[백준] 2206번 - 벽 부수고 이동하기 (파이썬)

문제) 백준 - 너비 우선 탐색 - 벽 부수고 이동하기

-> www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

좌표와 벽 부수는 게 가능한지에 대한 여부를 포함하는 index를 가진 3차원 dist 리스트를 선언한다. 

dist[1][3][1] = 1이라는 것은 2행 4열에서 벽을 1개 부실수 있고 거리가 1이라는 것이다.

이렇게 리스트를 설정했다면 bfs()를 통해 최단거리를 탐색하면서 (n - 1)행 (m - 1)열 일 때 해당하는 거리의 값을 return 하면 된다.

 

 

 

반성)

1. 3차원 리스트의 활용을 생각 못했다.

2. 이차원 그래프 형식으로 나오면 bfs(x, y) 꼴(틀에 박힌 사고방식)에 집착하려는 성향이 있다.

 

 

 

소스 코드)

from collections import deque
import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    q = deque()
    q.append([0, 0, 1])
    dist = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    dist[0][0][1] = 1
    while q:
        a, b, wall = q.popleft()
        if a == n - 1 and b == m - 1:
            return dist[a][b][wall]
        for i in range(4):
            x, y = a + dx[i], b + dy[i]
            if 0 <= x < n and 0 <= y < m:
                if graph[x][y] == 1 and wall == 1:
                    dist[x][y][0] = dist[a][b][1] + 1
                    q.append([x, y, 0])
                elif graph[x][y] == 0 and dist[x][y][wall] == 0:
                    dist[x][y][wall] = dist[a][b][wall] + 1
                    q.append([x, y, wall])
    return -1


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

graph = []
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))
print(bfs())