[파이썬] [BFS] 백준 2206 벽 부수고 이동하기

문제

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

2206번: 벽 부수고 이동하기

코드

from collections import deque
n,m=map(int, input().split())

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

visited=[[[0]*2 for _ in range(m)] for _ in range(n)]

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

def bfs():
    queue=deque()
    queue.append([0,0,0])
    visited[0][0][0]=1

    while queue:
        r,c,k=queue.popleft()

        if r==n-1 and c==m-1:
            return visited[r][c][k]

        for i in range(4):
            nx=r+dx[i]
            ny=c+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny]==1 and k==0:
                    visited[nx][ny][1]=visited[r][c][0]+1
                    queue.append([nx,ny,1])
                if graph[nx][ny]==0 and visited[nx][ny][k]==0:
                    visited[nx][ny][k]=visited[r][c][k]+1
                    queue.append([nx,ny,k])
    return -1

print(bfs())

생각 정리

visited[x][y][0]은 안부순 경로, visited[x][y][1]은 부순 경로

중간에 벽을 부순 경로는 그 이후의 경로부터는 벽을 지나갈 수 없으므로 벽이 아닌곳들만 탐색하면 되고,

중간에 벽을 부수지 않은 경로는 그 이후의 경로에서 벽을 부술 수 있는 선택권이 주어진다.

 

visited=[0]*2
#[0, 0]
visited=[[0]*2 for _ in range(3)]
#[[0, 0], [0, 0], [0, 0]]
visited=[[[0]*2 for _ in range(3)] for _ in range(2)]
#[[[0, 0], [0, 0], [0, 0]], [[0, 0], [0, 0], [0, 0]]]