[알고리즘] 백준 2206 (파이썬)

이 문제는 처음 풀 때 너무 어려웠다... 벽 부수기 횟수가 0인 것과 1인 것을 나눠서 생각하는 것은 알았는데 지나온 길을 다시 안지나가게 하려고 한 번 지나간 길을 -1로 표시하였더니 벽을 부수고 간게 -1로 바꿔놓아 벽을 부수지 않고 가는 길을 막아버린 것이다..

따라서 앞으로 이런 경로 문제를 풀 때 기존 리스트와 동일한 형태의 리스트를 하나 더 만들어 지나온길을 체크하는 방식으로 풀이를 하였다.

이 문제에서는 지나온 길에 남은 벽 부수기 횟수를 넣었다.

오늘 1달여만에 문제를 다시 풀었는데 틀렸습니다가 나와서 코드를 보았는데 엄청난 실수를 한 것이 있어 글을 쓴다.

우선 올바른 풀이를 보자

import sys
from collections import deque

input = sys.stdin.readline

height, width = map(int, input().split())

n = []

for i in range(height):
    n.append(list(map(int,input().rstrip())))

nm = [[[] for j in range(width)] for i in range(height)]

def bfs(i,j):
    queue = deque([[i,j,1,1]])

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

    nm[i][j].extend([0,1])

    while queue:

        a = queue.popleft()

        if a[0] == height-1 and a[1] == width-1:
            return a[3]

        for i in range(4):

            nx = a[0] + dx[i]
            ny = a[1] + dy[i]

            if 0 <= nx <= height-1 and 0 <= ny <= width-1 and a[2] not in nm[nx][ny]:
                if n[nx][ny] == 0:
                    nm[nx][ny].append(a[2])
                    queue.append([nx,ny,a[2],a[3]+1])


                elif n[nx][ny] == 1:
                    if a[2] == 0:
                        continue
                    else:
                        nm[nx][ny].append(a[2])
                        queue.append([nx,ny,0 ,a[3]+1])
    return -1

ans = bfs(0,0)
print(ans)

여기서 나는 리스트에서 1을 만날 경우 벽부수기 카운트가 1일 때

 elif n[nx][ny] == 1:
                    if a[2] == 0:
                        continue
                    else:
                        nm[nx][ny].append(a[2])
                        a[2] -= 1
                        queue.append([nx,ny,a[2] ,a[3]+1])

이런 식으로 풀었다.

여기서 주의할 점은 a를 pop하고 한 a에 대해서 4가지 case를 보기 때문에 한 경우에서 a를 변경하면 나머지 경우에 영향을 미친다.
(이 문제에선 만약 첫 nx ny에서 a[2] -1이 된다면, 나머지에선 벽부수기 횟수가 자동으로 0으로 되는 큰 오류가 일어난다)

오늘 이 문제 덕분에 bfs문제를 풀 때 pop한 원소는 그대로 써야함을 다시 한 번 배웠다!!