[BOJ] 2206 벽 부수고 이동하기 | Python

문제

백준 2206번 벽 부수고 이동하기 | 골드3

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

2206번: 벽 부수고 이동하기

• 알고리즘 분류 : 그래프 이론 | 그래프 탐색 | 너비 우선 탐색(BFS)

 

 

풀이 과정

파이썬 풀이

from collections import deque

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

def bfs(x, y):
    q = deque()
    q.append((x, y, 0))
    visited[x][y][0] = 1
    while q:
        x, y, wall = q.popleft()
        # x, y좌표와 wall(벽 부쉈는지 여부)

        if x == N-1 and y == M-1:
            return visited[x][y][wall]
            # 도착했다면 벽 부순 여부에 따른 visited 값 return

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny][wall]: 
                if not arr[nx][ny]:
                	# 방문한 적 없고 이동할 수 있으면(벽이 아니라면)
                    # (x, y) 값 + 1의 경로 남기고 q에 추가하기 
                    visited[nx][ny][wall] = visited[x][y][wall]+1
                    q.append((nx, ny, wall))
                if not wall and arr[nx][ny]:
                	# 만약 벽이 있는 곳인데 wall == 0이면 벽 부순 적이 없으므로 부수기 가능
                    # 벽 부쉈다는 의미로 visited[nx][ny] 중 인덱스 1의 위치에 경로 남기기 
                    visited[nx][ny][1] = visited[x][y][wall]+1
                    q.append((nx, ny, 1))
                    # wall = 1로 하여 벽 부쉈다는 표시
                    # 따라서 이후로는 벽이 있어도 추가로 벽을 부수지는 못함
    return -1
    # 불가능한 경우



N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
visited = [[[0, 0] for _ in range(M)] for _ in range(N)]
# 벽 부수지 않았을 때, 벽 부수고 난 뒤

print(bfs(0, 0))

• 3차원 배열의 visited를 통해 하나의 벽을 부순 여부에 따른 경로 기록
• 3차원 배열에 익숙하지 않을 때 풀었던 문제라 아이디어를 떠올리기도 힘들었고, 이해하는 과정에서도 시간이 다소 걸렸다.

예를 들어, 질문 게시판에 있는 반례 중 아래 반례로 코드를 실행시켜 visited를 확인해본다면 아래와 같은 결과가 나온다.

5 8
01000000
01010000
01010000
01010011
00010010

[[1, 3], [0, 12], [11, 3], [12, 4], [13, 5], [14, 6], [15, 7], [16, 8]]
[[2, 4], [0, 11], [10, 4], [0, 15], [14, 6], [15, 7], [16, 8], [17, 9]]
[[3, 5], [0, 10], [9, 5], [0, 16], [15, 7], [16, 8], [17, 9], [18, 10]]
[[4, 6], [0, 9], [8, 6], [0, 17], [16, 8], [17, 9], [0, 18], [0, 19]]
[[5, 7], [6, 6], [7, 7], [0, 18], [17, 9], [18, 10], [0, 19], [0, 20]]

즉 왼쪽은 벽을 뚫기 전 bfs를 통해 최단경로를 기록하던 것이지만 (N, M)의 위치까지 도달하지는 못하였고,

오른쪽은 벽을 뚫은 뒤 bfs를 통해 새로운 최단 경로를 기록한 것이다. 이 경우 (N, M)의 위치까지 도달하였으므로 결과는 20이 된다.