BOJ 2206 - 벽 부수고 이동하기

문제

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

 

 

풀이

BFS를 응용해서 문제를 해결한다

어떤 칸에 도달했을 때, 벽을 부수거나 부수지 않거나 두 가지의 상태가 있다

이것을 다음처럼 표현한다

visited[y][x][벽을 부숨, 벽을 부수지 않음]

visited[y][x][0]=0 # 벽을 부수지 않은 상태, 해당 위치를 방문하지 않은 상태
visited[y][x][0]=1 # 벽을 부수지 않은 상태, 해당 위치를 방문한 상태
visited[y][x][1]=0 # 벽을 부순 상태, 해당 위치를 방문하지 않은 상태
visited[y][x][1]=1 # 벽을 부순 상태, 해당 위치를 방문한 상태

 

또한 최단 거리를 저장하기 위해 visited[y][x][?] 에는 이전 칸에 값 + 1을 해준다

visited[next_y][next_x][?] = visited[y][x][?] + 1

 

이처럼 BFS를 사용하면 n*m 2차원 배열을 탐색하는데 2가지(벽을 부수거나 부수지 않았거나)를 추가해서 시간복잡도는 O(n*m*2)가 된다

 

 

코드

python

from collections import deque
 
 
def bfs():
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    q = deque([[0, 0, 0]])
    visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    visited[0][0][0] = 1
 
    while q:
        y, x, wall = q.popleft()
        if y == n - 1 and x == m - 1:
            return visited[y][x][wall]
 
        for d in range(4):
            next_y = y + dy[d]
            next_x = x + dx[d]
            if (
                0 <= next_y < n
                and 0 <= next_x < m
                and visited[next_y][next_x][wall] == 0
            ):
                if graph[next_y][next_x] == 0:
                    visited[next_y][next_x][wall] = visited[y][x][wall] + 1
                    q.append([next_y, next_x, wall])
                if wall == 0 and graph[next_y][next_x] == 1:
                    visited[next_y][next_x][1] = visited[y][x][0] + 1
                    q.append([next_y, next_x, 1])
 
    return -1
 
 
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
 
print(bfs())