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

 # 문제 링크 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 # 풀이 : 

개인적으로 이 문제의 핵심은 기존의 BFS문제가 2차원 구조를 다루었다면 이 문제는 3차원 구조를 다룬다는 것이다. 즉, 정점의 분화라고 표현하는데, 해당 정점에 대하여 고려해야할 정보가 늘어감에 따라 차원을 증가시켜 주는 것이다. 

<그림 1. 2차원 구조>

 위 그림1에서 사각형을 갈 수 없는 벽이라고 가정하고, start에서 출발하여 동서남북 4방향으로 이동할 때, end로 가는 최단 거리를 2차원 배열에 나타낸다면 4번만에 갈 수 있다. 그러나, 사각형을 거쳐가야만 갈 수 있는 곳은 가지 못한다는 의미로 -1이 됨을 알 수 있다. 만일, 모종의 장치로 인하여 벽을 뛰어넘을 수 있다면 어떻게 정보를 담아야 하는가?

<그림 2. 잘못된 2차원 구조>

 만일 위 그림이 맞다면, 사실상 사각형은 원형으로 바뀌어야 한다. 즉, 만나는 모든 벽을 뛰어 넘고, 그 횟수도 제한이 없다는 가정에서만 성립이 가능하다. 그러나 만일 문제의 조건이 벽을 뛰어 넘는 횟수가 정해져 있다거나, 벽을 만날 때 마다 뛰어넘지 않아도 End에 최소거리만에 도착할 수 있는 경우가 있다면 그림2의 2차원 배열은 정답을 구할 수 없다.

< 그림 3. 올바른 3차원 구조>

 만일 벽을 뛰어넘을 수 있는 횟수인 K가 최대 2번이라고 가정한다면, 올바른 3차원 구조는 그림과 같다. 우선, K = 0일때는 그림 1의 구조와 완전히 같다. 이제 K = 1일 때, 1행 2열을 보자. 1행 2열을 가기 위해서는 반드시 벽을 부숴야만 할 수 있다. 따라서 K = 1이고 1행 2열인, D[1][0][1]에 거리가 저장되어야 한다. 이 때 거리는 K = 0일 때 1행 1열로부터 왔으므로, D[1][0][1] = D[0][0][1] + 1이라 할 수 있다. 직관적으로 살펴보자. 1행 3열은 원형이다. 우선 1행 2열이 사각형이 아니라 원형이라고 가정한다면, 2칸을 건너야 1행 1열에서 1행 3열로 갈 수 있다. 그러나, 실제로는 1행 2열이 사각형, 즉 벽이므로 거리가 2칸이 걸리는 것은 맞으나, 벽을 하나 건너야 하기에 '2칸 걸리고 1개의 벽을 건넜다'는 뜻으로 K가 0이 아니라 1에 거리 2를 저장해야 한다. 

<그림 4. K의 상태에 따른 거리 변화>

 따라서, 만일 1st 벽을 현재 한번 건넜다면 현재 출발상태는 '2행 2열에 있으며 벽을 하나 부쉈다'로 표현이 가능하다. 따라서 행렬기준으로는 D[1][1][1]이라 할 수 있다. 따라서 2nd 벽을 이미 건너는 경우는 D[1][0][1]에 있다면, '1행 2열의 벽을 두번째 건너뛰는 경우'라면 반드시 첫번째 벽을 건너뛸때 1st 벽을 건너뛰어야 한다. 따라서 3차원 구조로는 같은 상태라 하더라도 벽을 각각 뛰어 넘는 경우, 그렇지 않는 경우를 모두 나타낼 수 있다. 그림 4에서 마찬가지로 1행 1열에서 1열 3행을 갈 때, 벽이 하나도 없다고 가정한다면 2칸만에 갈 수 있지만, 4칸이 걸려서도 갈 수는 있다. 그러나, 실제로 4칸이 걸리려면 벽을 두번 부숴야 하므로 K = 2인 상태인 1행 3열에 거리 4를 저장하는 것이다. 

 

 # 코드

import collections

# 동서남북 4방향을 나타내는 dr
dr = ((-1,0), (1,0), (0,-1), (0,1))

# bfs : 현재 k상태인 y열 x행에서 3차원 배열에 가능한 경우를 갱신하는 함수 
def bfs(y,x,k):
    global n, m
    queue = collections.deque()
    queue.append((y,x,k))
    # 시작지점에 초기값 1을 설정
    dist[y][x][k] = 1
    while queue:
        curr_y, curr_x, status = queue.popleft()
        for d in dr:
        	# next_y, next_x : 동서남북에 따른 다음 목적지의 행,열 정보
            next_y, next_x = curr_y+d[0], curr_x+d[1]
            # next_y와 next_x의 범위를 체크
            if 0<=next_y<n and 0<=next_x<m:
            	# 벽이 아니고 한번도 방문하지 않은 경우
                if MAP[next_y][next_x] == 0 and dist[next_y][next_x][status] == 0: 
                        dist[next_y][next_x][status] = dist[curr_y][curr_x][status]+1
                        queue.append((next_y,next_x,status))
                        
 				# 벽이고, 현재 벽을 한번도 부수지 않은 경우
                if status == 0: 
                    if MAP[next_y][next_x] == 1 and dist[next_y][next_x][status + 1] == 0: 
                            dist[next_y][next_x][status+1] = dist[curr_y][curr_x][status] + 1
                            queue.append((next_y, next_x, status+1))

n, m = map(int, input().split())
# 미로의 정보를 나타내는 MAP
MAP = [list(map(int, input())) for _ in range(n)]
# dist = 3차원 구조
dist = [[[0]*2 for _ in range(m)] for _ in range(n)]
# 1행 1열에서 출발
bfs(0,0,0)

# 벽을 부수지 않거나 하나만 부숴 갈 수 있다면 두값중 최소값
if dist[n-1][m-1][0] != 0 and dist[n-1][m-1][1]  != 0: 
    print(min(dist[n-1][m-1]))
    
# 벽을 안부수고 갈 때만 도착이 가능한 경우
elif dist[n-1][m-1][0] != 0: 
    print(dist[n-1][m-1][0])
    
# 벽을 무조건 한개를 부숴야만 도착이 가능한 경우
elif dist[n-1][m-1][1] != 0: 
    print(dist[n-1][m-1][1])
    
# 벽을 한번 부숴서도 가지 못하고 안부숴도 갈 수 없는 경우
else:
    print(-1)