[백준/Python] 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

이 문제는 방문리스트(visited)를 3차원 배열로 만드는 것이 핵심인 문제였다. 벽을 한번만 뚫을 수 있으므로 3차원으로 만들어야 한다.

visited[x][y][0] 에는 벽을 뚫지 않고 온 경우의 최단경로를 저장하고, visited[x][y][1] 에는 벽을 뚫고 온 경우의 최단경로를 저장한다.

 

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0] # 동서남북

def bfs(i, j):
    queue = deque([[i, j, 0]])
    visited = [[[0, 0] for _ in range(m)] for _ in range(n)] # 방문 확인 리스트
    visited[i][j][0] = 1 # 시작점은 벽을 안 부순 상태로 시작

    while queue:
        x, y, w = queue.popleft()
        if x == n-1 and y == m-1: # 이동하려는 위치에 도착하면 최단경로 리턴
            return visited[x][y][w]
        for i in range(4):
            # 다음에 이동할 위치
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny][w] == 0: # 이동 가능하며 아직 방문하지 않은 경우
                if graph[nx][ny] == 0: # 벽이 아니라면 이동
                    queue.append([nx, ny, w])
                    visited[nx][ny][w] = visited[x][y][w] + 1
                elif graph[nx][ny] == 1 and w == 0: # 벽이고 벽을 안 부순 상태라면 벽을 부수고 이동
                    queue.append([nx, ny, 1])
                    visited[nx][ny][1] = visited[x][y][w] + 1
    return -1 # 이동하려는 위치에 도달하지 못하는 경우 -1 리턴

print(bfs(0, 0))

1. 필요한 정보를 입력받고 필요한 변수를 생성한다.

2. BFS 탐색을 수행한다.

    2-1. visited를 생성하고 시작점은 벽을 안 부순 상태로 시작한다

    2-2. 이동하려는 위치에 도착하면 최단경로를 리턴한다

    2-3. 다음에 이동할 위치를 구한다.

    2-4. 이동 가능하며 아직 방문하지 않은 경우

        2-4-1. 벽이 아니라면 이동한다

        2-4-2. 벽이고 벽을 아직 안 부순 상태라면 벽을 부수고 이동한다

3. 모든 탐색이 끝난 후 이동하려는 위치에 도달하지 못하면 -1을 리턴한다

4. 결과를 출력한다