백준 2206 벽 부수고 이동하기

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/2206

이 문제는 전형적인 bfs문제이지만, 한 번만 벽을 부수고 이동할 수 있다는 점을 반영하여 (0, 0)에서 (n, m)까지 이동하는 최단 거리를 구하는 문제이다.

풀이

난이도 : GOLD III

처음에 떠올린 풀이는 bfs를 진행하다가 벽을 만날 경우 벽을 부수고 bfs를 다시 한 번 실행시켜 결과를 얻는 방법이었다. 하지만 이 방법은 bfs를 재귀적으로 실행해야하기 때문에 시간초과가 발생하여 포기하였다.

두 번째로 생각한 풀이 방법은 방문기록(visited)를 3차원 배열로 정의하여 벽을 부순 여부에 따라
'visited[벽을 부순 여부][x좌표][[y좌표]' 에 방문 기록을 기록하도록 하는 것이다.

1) q에 저장할 데이터 형태 : (x좌표, y좌표, 거리, 벽 부순 여부)
2) 벽을 이미 부수었는지 상태에 따라 visited를 다르게 기록
3) 처음 벽을 만날 경우 q에 벽 부순 여부를 True로 기록
4) 벽을 두 번이상 부수지 못하도록 관리

코드

from collections import deque

n, m = map(int, input().split())

array = []
for _ in range(n):
    array.append(list(str(input())))

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

# 방문기록을 3차원 배열로 기록
visited = [[[False] * m for _ in range(n)] for _ in range(2)]
visited[0][0][0] = True

q = deque()
q.append((0, 0, 1, False))

result = -1
while q:
    # x 좌표, y 좌표, 거리, 벽 부순 여부
    x, y, dist, isBreak = q.popleft()

    # 도착지점에 왔으면 정답 기록 후 종료
    if x == n - 1 and y == m - 1:
        result = dist
        break

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

        if nx < 0 or ny < 0 or nx >= n or ny>= m:
            continue

        if not isBreak:
            # 벽을 부수지 않은 상태
            if visited[0][nx][ny]:
                continue

            if array[nx][ny] == '1':
                # 이 부분이 벽이라면 visited[1][][]에 기록, isBreak = True로 기록
                visited[1][nx][ny] = True
                q.append((nx, ny, dist + 1, True))
            else:
                # 벽이 아니라면 visited[0][][]에 기록, isBreak = False로 기록
                visited[0][nx][ny] = True
                q.append((nx, ny, dist + 1, False))
        else:
            # 벽을 부순 상태
            if visited[1][nx][ny]:
                continue

            # 이미 벽을 부수었는데 또 벽일 경우 continue
            if array[nx][ny] == '1':
                continue
            
            visited[1][nx][ny] = True
            q.append((nx, ny, dist + 1, True))

print(result)