[탐색/BFS] 백준 2206 벽 부수고 이동하기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2206번: 벽 부수고 이동하기

 

 

 

2. 문제 풀이

 최단 경로를 찾는 문제로, 임의로 벽 1개를 부술 수 있습니다. 

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS 탐색으로 최적 경로를 탐색합니다.

 

 

 

3. 코드

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

# 입력
N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().rstrip())))

# bfs
dist = []  # 최단 경로 거리
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우

# 한 개씩 뚫어보고 탐색
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:  # 벽이 있으면 뚫어봄
            drilled_board = deepcopy(board)
            drilled_board[i][j] = 0

            # bfs
            visited = [[False]*M for _ in range(N)]
            queue = deque([(0, 0)])
            visited[0][0] = True
            while queue:
                x, y = queue.popleft()
                if x == N-1 and y == M-1:
                    dist.append(drilled_board[x][y])
                    break
                for dx, dy in direction:
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < N and 0 <= ny < M and drilled_board[nx][ny] == 0 and not visited[nx][ny]:
                        drilled_board[nx][ny] = drilled_board[x][y] + 1
                        queue.append((nx, ny))
                        visited[nx][ny] = True
# 경로가 하나라도 있다면 출력
if dist:
    print(min(dist)+1)
else:
    print(-1)

 브루트포스 방식으로, 벽 1개씩 제거하며 BFS탐색을 하면 시간 초과가 납니다... 벽의 개수만큼 BFS 탐색하므로 시간이 많이 소요됩니다.

 

 

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

# 입력
N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().rstrip())))

# bfs
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
queue = deque([(0, 0, 0)])
visited[0][0][0] = 1
while queue:
    x, y, is_drill = queue.popleft()
    if x == N-1 and y == M-1:
        print(visited[x][y][is_drill])
        break
    for dx, dy in direction:
        nx, ny = x+dx, y+dy
        if 0 <= nx < N and 0 <= ny < M:
            # 벽이 아니고, 방문하지 않은 곳이면 탐색
            if board[nx][ny] == 0 and visited[nx][ny][is_drill] == 0:
                visited[nx][ny][is_drill] = visited[x][y][is_drill] + 1
                queue.append((nx, ny, is_drill))

            # 아직 부숴본 적 없는 벽이라면 뚫고 탐색
            elif board[nx][ny] == 1 and is_drill == 0:
                visited[nx][ny][is_drill+1] = visited[x][y][is_drill] + 1
                queue.append((nx, ny, is_drill+1))
else:
    print(-1)

 그대신에 visited에 벽 부수기 유무(is_drill)를 추가하면 한 번에 bfs 탐색할 수 있습니다.