[백준] 벽 부수고 이동하기(골드3)

문제 링크

https://www.acmicpc.net/problem/2206

 

BFS 이용 문제

1. q에 넣는 정보: y, x, <한번 이미 벽을 부순 적이 있는지 여부>, 지금까지 온 거리 

 

2. 현재 인덱스에서 dy, dx 변수를 이용하여 상하좌우를 이동하며,

다음에 q에 넣어줄 인덱스(y, x)가 배열의 인덱스 범위를 벗어나지 않는지 확인

 

3. 벽이 아니고 아직 방문하지 않은 경우 / 벽이고 아직 벽을 부순적이 없는 경우로 

나누어  q에 삽입 

-> 벽인데 이미 벽을 한 번 부순적이 있는 경우는 자동으로 중단됨

 

4. 답을 return 

y, x가 n-1, m-1에 도달했을 경우 dist 변수 return

while문이 종료되었는데 dist가 return 되지 않은 경우

-> 0, 0에서 n-1, m-1로 가는 경로가 존재하지 않으니 -1 return

 

* 왜 visited 배열이 3차원 배열이어야 하는지?

한 번 벽을 부순 적이 있는 경우인지, 없는 경우인지 구분해야 하기 때문에 

 

구현 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(n, m, graph):
    visited = [[[False]*2 for _ in range(m)] for _ in range(n)]
    visited[0][0][0] = True
    q = deque([(0, 0, 0, 1)])

    while q:
        y, x, broken, dist = q.popleft()
        if (y, x) == (n-1, m-1):
            return dist

        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                # 벽이 아니고 아직 방문 안한 경우
                if graph[ny][nx] == 0 and not visited[ny][nx][broken]:
                    visited[ny][nx][broken] = True
                    q.append((ny, nx, broken, dist+1))
                # 벽이고 아직 벽을 부순 적이 없는 경우
                elif graph[ny][nx] == 1 and broken == 0 and not visited[ny][nx][1]:
                    visited[ny][nx][1] = True
                    q.append((ny, nx, 1, dist+1))

    return -1

n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]
print(bfs(n, m, graph))