BOJ 2206: 벽 부수고 이동하기 [Python 3]

오늘의 문제는 BOJ 2206, 벽 부수고 이동하기이다.

문제 내용은 단순히 bfs를 이용하면 될 것 같지만, 이동하면서 벽을 한 번 깰 수 있다는 조건이 있어서 기존의 방식으로 접근할 수 없었다.

 

from collections import deque
m,n= map(int,input().split())
data=[[1e10]*n]
for i in range(m):
    data.append([1e10]+list(map(int,list(input()))))
visited=[[[0,0] for _ in range(n+1)] for _ in range(m+1)]


q=deque()
q.append([1,1,0])
visited[1][1]=[1,1]
dx=[[0,1],[0,-1],[1,0],[-1,0]]

def bfs():
    if n==1 and m==1:
        return 1
    while q:
        x,y,brokenWall=q.popleft()
        for x1,y1 in dx:
            if 0<x+x1<m+1 and 0<y+y1<n+1:
                if x+x1==m and y+y1==n: 
                    return visited[x][y][brokenWall]+1
                if not visited[x+x1][y+y1][brokenWall]:
                    if not data[x+x1][y+y1]: 
                        visited[x+x1][y+y1][brokenWall]=visited[x][y][brokenWall]+1
                        q.append([x+x1,y+y1,brokenWall])
                    if not brokenWall and data[x+x1][y+y1]:  
                        visited[x+x1][y+y1][1]=(visited[x][y][brokenWall]+1)
                        q.append([x+x1,y+y1,1])
                        
                            
    return -1

print(bfs())

코드가 복잡하니 세세히 설명해보도록 하겠다.

먼저 좌표들을 input 받는다.

data에서 겉 면들은 벽과 구별하기 위해서 1e10으로 두었다. (굳이 그럴 필요 없긴 함... 어차피 뒤에서 걸러져서)

그리고 visited는 3차원 리스트로 두었다.

visited에서 data의 각 좌표의 크기만큼 0으로 input 받았다.

또한, 

visited[x좌표][y좌표][(밟았던 적이 있음)]에서,

(밟았던 적이 있음)을 (벽을 뚫어본 적이 없음, 있음)으로 분리해서 계산했다.

 

벽을 한 번 뚫었던 루트를 탄 사람들은 더 이상 벽을 뚫지 못하지만,

벽을 뚫어보지 못한 루트를 타면 추후에 벽을 뚫어서 길을 만들어 낼 수 있기 때문이다.

 

이제 BFS를 이용해서, 좌표를 한 칸 한 칸 움직인다.

여기서 만난 좌표가 가능한 좌표 중, 벽인 경우에는 벽을 뚫어보지 못한 루트만 통행이 가능하게끔 하고,

이제 벽을 뚫었음으로 벽을 뚫었던 좌표에 포함 시킨다.

가능한 좌표 중, 이동할 수 있는 일반 좌표이면 두 경우 모두 통행시킨다.

 

 

문제가 어려운 만큼, 설명하기도 복잡한 것 같다.

 

이해가 잘 안 되면 댓글 부탁드립니다...