[알고리즘/파이썬] 백준 2206 - 벽 부수고 이동하기

문제

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

2206번: 벽 부수고 이동하기

 

풀이

2달 전에 풀었던 문젠데 지금 다시 풀 때랑 2달 전 풀이랑 생각한게 똑~~같아서 놀랐다.

 

난 2달 전과 비교해서 발전한게 없다는 뜻인건가(...) 뭐 아무튼 ... bfs문제였고 visited에 해당 칸에 도달하기까지 가장 짧게 방문한 거리를 저장해두는 방식이다. 여기서 visited를 3차원으로 구성하는데 visited[2][2][1] 에 들어간 값의 의미는 (2,2) 칸에 도착할때까지 한 번 벽을 부쉈을 경우 최단거리.  라는 의미고, visited[2][2][0]에 들어간 값의 의미는 (2,2) 칸에 도착할 때까지 한 번도 벽을 부수지 않았을 경우의 최단거리. 라는 의미이다. 

 

nflag라는 값을 q에 넣어줌으로써 지금까지 벽을 한 번 부쉈는지 안 부쉈는지를 나타내고 해당 값을 사용해서 visited에 원하는 값을 넣어줄 수 있다.

 

코드

from collections import deque
n,m = map(int,input().split())
arr = []
for _ in range(n):
    tmp = input()
    tmp = [int(a) for a in tmp]
    arr.append(tmp)

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

answer = 1e9

def bfs(x,y):
    global answer
    visited = [[[1e9,1e9] for _ in range(m)] for _ in range(n)]
    q = deque()
    q.append((x,y,1,0))

    while q:
        nx,ny,nsum,nflag = q.popleft()

        if visited[nx][ny][nflag] > nsum:
            visited[nx][ny][nflag] = nsum
        else:
            continue
            
        if nx == n-1 and ny == m-1:
            answer = min(answer,nsum)
            continue
            
        
        for i in range(4):
            cx = nx + dx[i]
            cy = ny + dy[i]

            if cx<0 or cy<0 or cx>=n or cy>=m:
                continue

            if arr[cx][cy] == 0 :
                q.append((cx,cy,nsum + 1,nflag))

            else:
                if nflag == 0:
                    q.append((cx,cy,nsum + 1,1))

bfs(0,0)
if answer == 1e9:
    print(-1)
else:
    print(answer)