[백준][Python]2206번(벽 부수고 이동하기)

백준 2206번

✔️ 문제 풀이

◾ 방문체크

• 벽을 부수지 않은 경우와 벽을 부순 경우를 나눠서 방문체크를 해주는 것이 이 문제의 관건
• 부순적 없는 경우는 uvisited에, 부순적 있는 경우는 bvisited에 방문 체크를 해준다.
• 큐에서 값을 꺼낼 때마다 케이스를 3가지로 나누어서 분기한다
  1) 다음 접근하려는 곳이 0이며, 벽을 부순적이 없을 때
  ⇒ uvisited에 방문체크 후 큐에 입력
  2) 다음 접근하려는 곳이 0이며, 벽을 부순적이 있을 때
  ⇒ bivisted에 방문체크 후 큐에 입력
  3) 다음 접근하려는 곳이 1이며, 벽을 부순적이 없을 때
  ⇒ bvisited에 방문체크 후 큐에 입력
• 이때 2)와 3) 케이스 모두 bvisted에 방문체크를 하지만 이전 방문에 대한 값을 가져오는 리스트가 다르다.
• 2)의 경우, 이미 bvisted에서 방문체크가 이루어지고 있었기 때문에 bvisted에서 값을 가져온다
• 3)의 경우, uvisited에서 방문체크가 이루어지다가 처음 벽을 부수는 경우이기 때문에 uvisited에서 값을 가져온다
• 3)의 경우, 방문하려는 곳이 벽을 뚫지 않고도 접근할 수 있는 곳이라면 bvisited에서 방문 체크를 하면 안되기 때문에 같은 인덱스의 uvisited 값이 존재한다면 값을 업데이트하지 않는다.

최종 제출 코드

from collections import deque

n, m = map(int, input().split())
grid = [input() for _ in range(n)]

q = deque()
q.append((0, 0, 0))
uvisited = [[0]*m for i in range(n)]
uvisited[0][0] = 1
bvisited = [[0]*m for i in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while q:
  
  x, y, broken = q.popleft()
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if nx < 0 or ny < 0 or nx >= m or ny >= n:
      continue

    if grid[ny][nx] == '0' and not broken:
      if uvisited[ny][nx] > uvisited[y][x]+1 or not uvisited[ny][nx]:
        uvisited[ny][nx] = uvisited[y][x]+1
        q.append((nx, ny, 0))
    elif grid[ny][nx] == '0' and broken:
      if bvisited[ny][nx] > bvisited[y][x]+1 or not bvisited[ny][nx]:
        bvisited[ny][nx] = bvisited[y][x]+1
        q.append((nx, ny, 1))
    elif grid[ny][nx] == '1' and not broken:
      if (bvisited[ny][nx] > uvisited[y][x]+1 or not bvisited[ny][nx]) and not uvisited[ny][nx]:
        bvisited[ny][nx] = uvisited[y][x]+1
        q.append((nx, ny, 1))

if not bvisited[n-1][m-1] and not uvisited[n-1][m-1]:
  print(-1)
elif not bvisited[n-1][m-1] or not uvisited[n-1][m-1]:
  print(bvisited[n-1][m-1]+uvisited[n-1][m-1])
else:
  print(min(bvisited[n-1][m-1], uvisited[n-1][m-1]))

✔️ 실행 결과