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

문제링크: 2206번: 벽 부수고 이동하기 (acmicpc.net)

2206번: 벽 부수고 이동하기

 

이 문제는 기본적인 미로찾기 문제에서 벽을 처음부터 끝까지 이동하면서 총 한 번 부술 수 있다는 조건을 추가한 문제이다. 처음에는 기본적인 미로찾기 문제를 해결하는 BFS 알고리즘을 사용하면서 벽을 부수는 카운트를 추가하고, 기존의 미로찾기 문제처럼 미로의 행렬만큼의 visited를 만들어서 방문하지 않은(0)인 곳만 찾아다니고 방문한 곳은 (1)로 바꾸어 가며 최단거리를 찾으려고 했었다. 그렇게 문제를 풀면 생기는 문제가 있는데, 아래와 같이 행렬이 주어진 경우에서 눈으로 보면 (0,5)의 벽을 부수고 가야지만 (1,5)에 도달할 수 있다.

2 6
010001
000110

1. 큐에 (0,0) 이 반환되고 갈 수 있는 (1,0), 벽을 부순 (0,1)이 큐에 들어간다.

2. 벽을 부순 (0,1)이 (0,2) 로 진행하는 경우에 visited[0][2]를 방문 표시한다.

3. 1에서 (1,0)으로 벽을 기준으로 돌아가던 루트는 (0,2)가 이미 방문 표시되어 있어 가지 못해서 (0,6)의 벽을 부수고 (2,6)에 도달하는 경우가 막히게 된다.

 

그래서 나는 풀이과정을 DFS알고리즘으로 돌려야 하나 싶었지만 BFS로 풀고 싶어 벽을 한번 부순 경우의 루트에서의 visited 방문처리와 벽을 한번도 부수지 않은 visited 방문처리를 다르게 하며 BFS를 사용하여 문제를 풀어 보았다.

import sys
from collections import deque

N,M=map(int,sys.stdin.readline().rstrip().split())

lst=[[] for _ in range(N)]

for i in range(N):
    x=sys.stdin.readline().rstrip()
    for j in list(str(x)):
        lst[i].append(int(j))

def bfs():
    dx=[1,-1,0,0]
    dy=[0,0,-1,1]
    que=deque()
    que.append((0,0,0))
    time=1
    end=0
    visited=[[0 for _ in range(M)] for _ in range(N)]
    visited[0][0]=2
    while que:
        for i in range(len(que)):
            x,y,wall=que.popleft() #wall은 벽을 한번 부쉈으면 1, 부순 적 없으면 0
            if x==M-1 and y==N-1:
                end=1
                return time
            for j in range(4):
                xmv=x+dx[j]
                ymv=y+dy[j]
                if 0<=xmv<M and 0<=ymv<N:
                    if lst[ymv][xmv]==0:
                        if wall==1 and visited[ymv][xmv]==0:
                            visited[ymv][xmv]=1 #벽을 부순 루트는 방문을 1로처리
                            que.append((xmv,ymv,wall))
                        elif wall==0 and visited[ymv][xmv]<2: #벽을 부수지 않는 루트는 벽을 부수고 간 루트가 방문한 곳으로 갈 수 있다.
                            visited[ymv][xmv]=2 #벽을 부수지 않고 가는 루트는 방문을 2로처리
                            que.append((xmv,ymv,wall))
                    if lst[ymv][xmv]==1 and wall==0 and visited[ymv][xmv]==0: #벽 마주했을때 부수는 경우
                        visited[ymv][xmv]=1
                        que.append((xmv,ymv,wall+1))
        time+=1
    if end==0:
        return -1
                    
print(bfs())

 

코드를 보다싶이 벽을 부순 경우의 루트는 방문을 1로 표시하고, 벽을 안부순 경우의 루트는 2로 표시하였다. 만약 벽때문에 돌아가야 하는 경우가 있다면 무조건 벽을 한번 부수고 간 루트가 빠르기 때문에 벽을 부수지 않는 루트는 visited가 0또는 1일때, 벽을 부수고 간 루트가 방문한 노드 (visted=1)로 갈 수 있도록 했다. 반대로 벽을 부순 루트는 벽을 안부순 루트보다 더 빠르기 때문에, 혹 겹치더라도 같은 시간내에 같은 위치에 방문할 수 있다면 벽을 안부수고 가는 것이 더 효율적이기에, visited가 0일 때만 진행 할 수 있도록 했다.