[Baekjoon] 2206 - 벽 부수고 이동하기 (BFS)
🧐 문제 설명
😍 나의 풀이
최근에 백준 BFS 문제를 많이 풀이해서 이 문제도 쉽겠다고 생각했는데 상당히 까다로웠다.
처음 접근한 방식의 문제점
부술 수 있는 벽('1')의 후보 좌표들을 다 뽑아서 하나씩 부숴보고 BFS 탐색을 했다. (Brute Force)
→ 그래프의 가로, 세로 길이가 N, M이기 때문에 그래프의 크기는 NxM이다. 그런데, 이 크기를 벽의 개수만큼 탐색해야하기 때문에 최악의 경우(모두 벽으로 이루어져있는 경우) O((NxM)^2)의 시간복잡도가 나오므로 시간초과가 나왔다.
두 번째 접근한 방식의 문제점
visited 리스트를 [방문 여부(경로 길이), 벽 부술 수 있는 횟수] 를 3중 리스트로 만들어서 풀이했다.
대략적인 유사코드를 적어보자면,
if graph[다음 탐색할 지점] == 0: # 벽 만나지 않는 경우
visited[방문 여부] = True
if graph[다음 탐색할 지점] == 1 and 벽 부술 수 있는 횟수 == 1:
# 벽을 만났고 벽 부술 수 있는 횟수가 남아있는 경우
visited[방문 여부] = True
visited[벽 부술 수 있는 횟수] = 0이렇게 작성했는데 예시 테스트 케이스는 통과했지만 정답에는 실패했다.
예를 들어서 빨간 색 경로는 (0,1)에 위치한 1을 만나면 벽을 부술 수 있기 때문에 벽을 부수고 진행하다 또 만나는 1 때문에 목적지에 도착할 수 없어서 -1을 반환한다. 하지만, 파란색 경로는 1을 한 번만 부수고도 도착할 수 있으므로 최단 경로가 12가 된다.
즉, 벽을 부수지 않고 가는 것이 최단 경로가 될 수 있다는 약간의 Greedy한 아이디어가 필요했다.
→ 따라서 visited 리스트를 그 지점에 도달하기 전까지 [벽을 부수고 와서 도착한 경로의 길이, 벽을 부수지 않고 도착한 경로의 길이]로 나누어 생각해줘야 한다.
from collections import deque
N, M = map(int, input().split())
graph =[]
for i in range(N):
graph.append(list(map(int, input())))
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)] # 방문 처리 리스트 [[벽 부순 적 O?, 벽 부순 적 X?] * M] * N개
visited[0][0][1] = 1
def bfs():
queue = deque([[0, 0, 1]]) # 초기 출발 좌표 (0, 0) & 처음에는 벽 부순 적 없으니까 1
dx = [-1, 1, 0, 0] # 좌우
dy = [0, 0, -1, 1] # 상하
while queue:
y, x, w = queue.popleft()
if y == N-1 and x == M-1: # 도착
return visited[y][x][w]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<M and 0<=ny<N:
if graph[ny][nx] == 0 and visited[ny][nx][w] == 0:
visited[ny][nx][w] = visited[y][x][w] + 1 # 경로 길이
queue.append([ny, nx, w])
if graph[ny][nx] == 1 and w == 1: # 벽을 만났을 때 벽 부술 수 있는 횟수가 남아 있으면
visited[ny][nx][0] = visited[y][x][1] + 1 # 벽 부수고, 벽 부순적 있는 인덱스 값(0)으로 이전 위치 값 + 1 경로길이 할당
queue.append([ny, nx, 0])
return -1
print(bfs())👏 다른 사람의 풀이
이 문제의 아이디어를 얻을 수 있게 해준 좋은 풀이 설명을 첨부한다.
