[Python] 백준 2206번: 벽 부수고 이동하기

www.acmicpc.net/problem/2206

import sys
input = sys.stdin.readline

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


def bfs():
    global stepMap

    todo = [(0, 0, 0)]
    
    while todo:
        curPos = todo.pop(0)
        if curPos[1] == N-1 and curPos[2] == M-1:
            return stepMap[curPos[0]][curPos[1]][curPos[2]]

        for i in range(4):
            curX, curY = curPos[1] + dx[i], curPos[2] + dy[i]

            if 0 <= curX <= N-1 and 0 <= curY <= M-1:
                if map[curX][curY] == 0 and stepMap[curPos[0]][curX][curY] == 0:
                    stepMap[curPos[0]][curX][curY] = stepMap[curPos[0]
                                                             ][curPos[1]][curPos[2]]+1
                    todo.append((curPos[0], curX, curY))
                elif map[curX][curY] == 1 and stepMap[1][curX][curY] == 0 and curPos[0] == 0:
                    stepMap[1][curX][curY] = stepMap[curPos[0]
                                                     ][curPos[1]][curPos[2]]+1
                    todo.append((1, curX, curY))
    return -1


N, M = map(int, input().split())
map = []

for i in range(N):
    curLine = input().rstrip()
    curList = []
    for j in range(M):
        n = int(curLine[j])
        curList.append(n)
    map.append(curList)


stepMap = [[[0]*M for _ in range(N)] for _ in range(2)]
stepMap[0][0][0] = 1

print(bfs())

기본적으로 bfs를 진행한다.

 

여기서 핵심은 stepMap이 (0,0)~(N-1,M-1) 배열을 2개를 담고 있다는 것이다.

stepMap[0][x][y]는 아직 벽을 부수지 않았을 때의 이동 카운트를 나타내며,

stepMap[1][x][y]는 벽을 1번 부쉈을 때의 이동 카운트를 나타낸다.

 

각 탐색을 할 때 경우의 수가 4개가 있다.

1. map이 0이면서 벽을 뚫은 적이 없음(curPos[0]==0)

2. map이 1이면서 벽을 뚫은 적이 없음(curPos[0]==0)

3. map이 0이면서 벽을 뚫은 적이 있음(curPos[0]==1)

4. map이 1이면서 벽을 뚫은 적이 있음(curPos[0]==1)

 

여기서 다음 노드로 탐색을 허용하는 경우는 굵게 표시한 1, 2, 3번이다.

여기서 오로지 2번의 경우에만 벽을 뚫게 된다.

 

여담으로, dfs를 시도해보았으나, 최대 1000*1000번을 재귀를 사용하여 메모리가 초과하는 문제로 풀지 못하였다. 비트마스크로 메모리를 절약을 해도 불가능하였다.