[백준 #2206 파이썬] 벽 부수고 이동하기
이건 사실 내가 풀었다고 할 수 없는 문제였다! 결정적인 풀이는 참고를 했기 때문에 ㅎ
다만 기록과 반성을 위해서, 그리고 새로운 bfs 풀이에 대한 개념을 위해서 작성하는 오답노트
생각한 문제
1. 어떤 벽에 1을 써야 하는가, (아예 막혀 무조건 뚫어야 하는 경우, 무조건 뚫지 않아도 되는 경우로 구분해서 생각을 시작했다)
2. 두개이상의 방향으로 나아갈 수 있다면 어떤 방법으로 가는 것이 좋은가?
구현
사실 2번은 어느정도 경험해 본 문제였다!
풀던 방법은
1. 이동하는 케이스의 경우 cnt 변수를 만들어서 하나씩 더해주는 방식
2. max나 min을 값을 비교하며 갱신하는 방법
3. 현재 위치의 값에서 1을 더해서 이동하는 값에 대입해주는 방식이었다.
그래서 이러한 방식으로 어느정도 해결법을 찾아둘 수 있었다.
그런데 1은 처음 보고 알고 있는 수준에서는 완전탐색? 정도로 생각해볼 수 있겠다 싶었는데, 경우의 수가 워낙 많아지는 것 같아 포기 그래서 답을 찾아보던 중 새로운 방법을 배웠다
비트마스킹의 응용
익숙한 flag 개념이다. 알고리즘을 풀때 자주 사용하는 0과 1로 문제를 풀어보는 방법이다! 0은 물론 false, 방문하지 않음 등의 의미로 사용하고는 한다. 여기서 우리가 일반적으로 판단하는 방문 여부를 응용해보는 것이다.
visited = [[[0]*2 for _ in range(m)] for _ in range(n)]한 노드마다 방문여부를 두 개 만들어 주는 것이다! 이 방법이 왜 필요했냐면, 1이된 경우는 벽을 뚫고 난 다음의 시나리오, 0인 경우는 아직 벽을 뚫기 전의 시나리오를 구분해 주기 위한 장치다.(물론 반대로 생각해도 됩니다!)
그래서 벽을 뚫은 뒤에는 오직 뚫은 이후의 최소거리 숫자만 증가시키는 방식으로 최소 거리를 구하는 방법이다.
예를 들어 [0,0] 이 상태에서 벽을 뚫지 않은 경우에는 [0,0]..[1,0]...[2,0]으로 증가를하다가
벽을 만나서 뚫고난 이후에는 [0,3]...[0,4]..[0,5] 이런 방식으로 증가를 하는 것이다.
참으로 신박했지만, 새롭게 드는 생각
벽을 뚫긴 뚫는데 그 벽이 최소거리 벽이 아니면 어떡하지?
물론 최적의 벽이 아닐 수 있다, 이때 이 비트마스킹의 진가가 드러난다!
그래서 [벽을 뚫기 전의 시나리오, 벽을 뚫은 이후의 시나리오]두개 모두를 저장할 수 있게끔 공간을 만든거다.
그러나 벽을 뚫은 이후의 시나리오는,
다시 1을 처리해야 하는 상황이 오면 노드의 계산은 중간에 멈추고 큐에 추가되지 않아 탈락한다.
상하좌우 네가지 방향에 대해 모두 시도해보고 결론내는 결과기 때문에 마지막에 도착하는 값이 최적의 값이 된다.
다양한 테스트 케이스를 생각해보자!
공부하면서 배운 개념들
1. 비트마스킹을 새로운 차원을 만들어 값을 저장해서 사용하기
2. index out of range인데 이상이 없으면 input에서 이상이 없었나 확인하기
3. 완전탐색을 생각해보는 것도 좋지만 먼저 dp처럼 효율적인 방식을 먼저 생각해보기
from collections import deque
n,m = map(int,input().split())
room = [list(map(int,input()))for _ in range(n)]
visited = [[[0]*2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1
dx = [0,0,-1,1]
dy = [-1,1,0,0]
def bfs(a,b,c):
q = deque()
q.append((a,b,c))
while q:
x,y,z = q.popleft()
if x == n-1 and y == m-1:
return visited[x][y][z]
for i in range(4):
nx,ny = dx[i]+ x, dy[i] + y
if 0<=nx<n and 0<=ny<m:
# 벽을 마주친 경우
if room[nx][ny] == 1 and z == 0:
visited[nx][ny][1] = visited[x][y][0] + 1
q.append((nx,ny,1))
# 0을 마주친 경우 방문 처리
elif room[nx][ny] == 0 and not visited[nx][ny][z]:
visited[nx][ny][z] = visited[x][y][z] + 1
q.append((nx,ny,z))
return -1
print(bfs(0,0,0))