코드

from collections import deque

n, m = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int, input())))
    
# 3차원 행렬 => 마지막 요소 : 벽 파괴 가능 유무 확인
# visited[x][y][0] : 벽을 뚫지 않고 x, y까지 도착하는 경우
# visited[x][y][1] : 벽을 뚫고 x, y까지 도착하는 경우
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

visited[0][0][0] = 1

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

def bfs(x, y, z):
    q = deque()
    q.append((x, y, z))
    
    while q:
        x, y, z = q.popleft()
        
        # 끝 점에 도달하면 이동 횟수 출력
        # 도달했으면 끝까지 갈 수 있다는 의미
        if x == (n-1) and y == (m-1):
            return visited[x][y][z]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 맵을 벗어나면 반복 넘김
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
                
            # 다음 이동할 곳이 벽이고, 벽을 파괴하지 않은 경우
            if graph[nx][ny] == 1 and z == 0:
                visited[nx][ny][1] = visited[x][y][0] + 1
                
                # z를 1로 넘김 => 벽을 파괴했으므로 1
                q.append((nx, ny, 1))
            # 다음 이동할 곳이 벽이 아니고, 방문한 적이 없으면
            elif graph[nx][ny] == 0 and visited[nx][ny][z] == 0:
                visited[nx][ny][z] = visited[x][y][z] + 1
                q.append((nx, ny, z))
    return -1
    
    
print(bfs(0, 0, 0))

문제 해설

BFS의 심화 문제.

‘벽을 한 번 뚫을 수 있다’ 라는 심플한 조건이 생겼을 뿐인데, 문제에 접근하는 것이 어려워 구글링을 하였다. DFS, BFS 문제를 어렵게 내면 정말 심화될 수 있다는 것을 깨닫게 해준 문제…

문제 풀이 참고 블로그

벽은 단 한 번만 뚫을 수 있으므로, 3차원 배열로 벽을 뚫었는지 뚫지 않았는지 두 경우에 대한 최단 거리를 각각 기록하여, 마지막까지 도착한 경우의 값을 정답으로 출력하면 된다. 이 때, x와 y가 마지막까지 도달하지 못하는 경우는 -1을 return 해줌으로써 문제를 해결할 수 있다.

댓글남기기

참고