[Python/파이썬] 백준 알고리즘 2206번 - 벽 부수고 이동하기 (BFS)

 

 

 

<풀이>

처음에는 백트래킹으로 접근하려고 했다.

"""
1. 아이디어
- 백트래킹으로 탐색하며 벽을 뚫을 때와 안뚫을 떄를 구분하여 전체 가지수를 탐색한다.

2. 시간 복잡도
- O(N * M) : 1000 * 1000 = 1,000,000     -> 가능

3. 변수
- N, M : int
- map : int[][]
- visit : bool[][]
"""
import sys
sys.setrecursionlimit(10 ** 6)
INF = sys.maxsize

input = sys.stdin.readline

N, M = map(int, input().split())

map = [list(map(int, input().rstrip())) for _ in range(N)]
visit = [[False] * M for _ in range(N)]

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

min_dist = INF


def backtracking(x, y, dist, break_the_wall):
    if x == N - 1 and y == M - 1:
        global min_dist
        if dist < min_dist:
            min_dist = dist
        return
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if not visit[nx][ny]:
                    if map[nx][ny] == 0:
                        visit[nx][ny] = True
                        backtracking(nx, ny, dist + 1, break_the_wall)
                        visit[nx][ny] = False
                    elif map[nx][ny] == 1 and break_the_wall == False:
                        visit[nx][ny] = True
                        backtracking(nx, ny, dist + 1, True)
                        visit[nx][ny] = False


backtracking(0, 0, 1, False)

print(min_dist if min_dist < INF - 1 else -1)

좌표 x, y뿐만 아니라 현재 거리 값인 dist와 벽을 뚫었는지 여부를 저장하는 bool 타입의 break_the_wall을 이용해서 전체 경우의 수를 조사하고 목표 좌표에 도달한 경우 글로벌 변수인 min_dist와 현재 dist를 비교해 더 작다면 바꿔주는 방식으로 알고리즘을 작성해 주었다.

 

이렇게 문제를 푼 후 문제에서 주어진 예제 입출력을 확인해보니 모두 맞았다.

 

하지만 제출을 하자 시간 초과가 떴다.

필자가 시간 복잡도 계산을 잘못한 결과였다.

단순히 모든 노드를 조사하므로 N * M이 걸릴거라 예상했지만 최단 경로로 가는 경우의 수만 생각해도 NM! / N! * M!이다. 따라서 시간 초과가 나올 수밖에 없었다.

 

이를 해결하기 위해 다른 방법으로 문제를 접근해보았다.

새로운 접근 방법은 3차원 배열을 활용한 BFS였다.

"""
1. 아이디어
- 3차원의 방문 여부 배열을 만들고 z축에서 0이면 아직 벽을 부수지 않은 경우, 1이면 벽을 부순 경우로 생각하여 BFS로 탐색한다.

2. 시간 복잡도
- O(2NM + 8NM) : 10 * 1000 * 1000 = 10,000,000     -> 가능

3. 변수
- N, M : int
- map : int[][]
- visit : int[][][]
"""
import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())

map = [list(map(int, input().rstrip())) for _ in range(N)]
visit = [[[0] * 2 for _ in range(M)] for _ in range(N)]

q = deque()
q.append([0, 0, 0])
visit[0][0][0] = 1

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

while q:
    x, y, z = q.popleft()
    if x == N - 1 and y == M - 1:
        print(visit[x][y][z])
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            # 이동할 곳이 벽이고 벽 파괴 기회를 사용 하지 않은 경우
            if map[nx][ny] == 1 and z == 0:
                visit[nx][ny][1] = visit[x][y][z] + 1
                q.append([nx, ny, 1])
            # 이동할 곳이 벽이 아니고 아직 방문 하지 않은 경우
            elif map[nx][ny] == 0 and not visit[nx][ny][z]:
                visit[nx][ny][z] = visit[x][y][z] + 1
                q.append([nx, ny, z])
else:
    print(-1)

이 풀이에서 특징적인 것은 방문 여부 배열인 visit이 3차원 배열이고 단순히 False, True로 값을 채워넣는 것이 아니라 int 값을 집어넣어 거리 값을 표현했다는 것이다.

visit 배열에서 첫번째 인덱스는 x, 두번째 인덱스는 y, 그리고 마지막 인덱스는 벽 파괴 기회 사용 여부를 나타냈다.

값이 0인 경우 아직 벽 파괴 기회를 사용하지 않은 경우고 1인 경우는 벽 파괴를 이미 한 번 한 경우이다.

(visit[x][y][0]은 벽 파괴 X / visit[x][y][1]은 벽 파괴 O)

 

BFS는 너비 우선 탐색이므로 가장 먼저 목표 좌표에 도달했을 때가 최단 거리 값을 갖는다.

따라서 if 문을 통해 목표 좌표에 도달한 경우 해당 visit 배열에 들어있는 값을 출력하고 break하도록 하였다.

while문을 다 돌아 queue가 비었음에도 목표 좌표에 도달하지 못한 경우 while-else문으로 -1을 출력하게 하였다.

 

 

 

<핵심 정리>

1. 3차원 배열을 활용한 BFS를 통해 특정 조건을 포함한 그래프 탐색을 진행할 수 있다.

2. visit에 True, False가 아닌 int 값을 채워넣어 거리 값을 저장할 수도 있다.

3. BFS는 너비 우선 탐색이므로 제일 먼저 목표에 도달한 경우가 가장 빨리 도달한 경우이다.