백준 2206 벽 부수고 이동하기

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

 

 이 문제는 벽을 한번만 뚫을 수 있을 때, 0,0에서 시작해서 N-1,M-1까지의 최단거리를 구하는 문제이다.

 

 이 문제는 간단한 BFS로 풀 수 있을것만 같았지만, 필자는 나름 헤맸다. 맨 처음의 생각은 그래프 위를 지나가는 어떠한 인자가 벽을 뚫을 수 있는가,거리는 얼마인가를 들고 다니면서 계산을 하는 것이었다. 하지만 이렇게 한다면 방문처리나 거리 같은 것을 일일이 큐에 저장해야 하기에 메모리에 부담이 된다.

 

그렇기에 아예 방문처리와 거리를 하나로 처리해버리고, 방문 리스트를 3차원으로 만들어 벽을 뚫었을 때, 벽을 안 뚫었을 때를 따로 기록하고, BFS의 특징 상 가장 먼저 N-1,M-1에 도착하면 그것이 최소거리이기에 바로 리턴해버리는 식으로 풀었다.

 

import sys
input = sys.stdin.readline
from collections import deque

def BFS():
    que = deque()
    que.appendleft([0,0,0])#현NM,벽뚫기
    v=[[[0,0] for _ in range(M)] for _ in range(N)]

    while que:
        nN,nM,w = que.pop()
        if nN==N-1 and nM==M-1:
            return v[nN][nM][w]+1
        for a in range(4):
            aN,aM = nN+dN[a],nM+dM[a]
            if 0<=aN<N and 0<=aM<M:
                if graph[aN][aM]=='0' and v[aN][aM][w]==0:
                    v[aN][aM][w] = v[nN][nM][w]+1
                    que.appendleft([aN,aM,w])
                elif graph[aN][aM] == '1' and w==0:
                    v[aN][aM][1]=v[nN][nM][0]+1
                    que.appendleft([aN,aM,1])

    
    return -1



N,M = map(int,input().rstrip().split())
graph=[]
dN,dM=[1,-1,0,0],[0,0,1,-1]

for _ in range(N):
    graph.append(input().rstrip())

print(BFS())