[BOJ 2206] 벽 부수고 이동하기 (Python3)

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

from collections import deque
 
N, M=map(int, input().split())
graph=[]
dist=[[[0,0] for _ in range(M)] for _ in range(N)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
for i in range(N):
    graph.append(list(map(int, input())))
 
def bfs(x,y,flag):
    queue=deque()
    queue.append((x,y,flag))
    dist[x][y][flag]=1
    while queue:
        x,y,flag=queue.popleft()
        if x==N-1 and y==M-1:
            return dist[N-1][M-1][flag]
        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 dist[nx][ny][flag]!=0:
                continue
            if graph[nx][ny]==0:
                dist[nx][ny][flag]=dist[x][y][flag]+1
                queue.append((nx,ny,flag))
            if graph[nx][ny]==1 and flag==0:
                dist[nx][ny][1]=dist[x][y][flag]+1
                queue.append((nx,ny,1))
    return -1
 
print(bfs(0,0,0))
 

역.쉬 골드4 ^0^ 나에겐 너무 버겁다고욧!

그래서 구.글.신을 참조했다~~ 

 

해답은 의외로 간단했다. 

flag값을 사용하기 위해 3차원 배열을 만든다.

 

(0,0) 부터 bfs로 탐색 후 방문하지 않은 길(0)이 있으면 dist 배열+1 한다. 방문하지 않은 벽을 만났고, flag값이 0(한번도 벽을 깬 적 없으면) flag 를 1로 바꿔주고 큐에 (nx, ny, 1) 을 넣어 한번 벽을 깼음을 나타낸다.

큐에서 목표 지점을 만나면 해당 인덱스의 dist 값을 리턴한다.