[BOJ 1987 파이썬] 벽 부수고 이동하기 BFS

 

2206번: 벽 부수고 이동하기

 

문제

---

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

---

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

---

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

예제 입력 1 

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1 

15

 

예제 입력 2 

4 4
0111
1111
1111
1110

예제 출력 2 

-1

 

첫번째 접근

---

BFS 특성 상 경로를 특정 짓기가 어렵다고 생각을 했다.

 

1. 일단 BFS_A를 돌린다

2. 0이면 단순 BFS처럼 진행하지만 1을 만나면 거기에서 새로운 BFS_B를 재귀호출한다.

3. BFS_B는 1을 벽으로 생각하고 너비 우선 탐색을 쭉 한다.

4. N,M에 도달했을 때, 최솟값을 찾는다

 

생각이 번뜩나서, 신나서 풀었다.

하지만.. 시간초과.

사실 지금껏 반복문을 돌리면서 BFS를 여러번 돌리는 문제가 많았고 이 문제도 그 형태와 비슷하다고 생각했지만, 그런 문제들과는 N과M의 범위 자체가 차원이 달랐다.

 

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

16236번: 아기 상어

BFS를 여러번 써야만 하는 문제의 예인데, 이 문제는 N의 범의가 20밖에 되지 않는다..

 

우선 실패한 코드를 보자.

from collections import deque
from copy import deepcopy
import sys

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

board = []

for i in range(N):
    board.append(list(map(int,list(sys.stdin.readline().rstrip()))))

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

visited = [[False for _ in range(M)] for __ in range(N)]

answer = 1e9

def bfs_before():
    global answer
    queue = deque()
    queue.append((0,0))
    visited[0][0] = True
    queue.append(-1)
    time = 1
    while queue:
        temp = queue.popleft()

        if temp == -1:
            if queue:
                time += 1
                queue.append(-1)
            else:
                return
        else:
            y,x = temp
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < M and 0 <= ny < N:
                    if not visited[ny][nx]:
                        visited[ny][nx] = True
                        if ny == N-1 and nx == M-1:
                            answer = min(answer,time+1)
                        if board[ny][nx] == 1:
                            bfs_after(ny,nx,visited,time+1)
                        else:
                            queue.append((ny,nx))

def bfs_after(by,bx,visited_after,time):
    global answer
    queue = deque()
    queue.append((by,bx))
    queue.append(-1)
    time_after = time
    new_visited = deepcopy(visited_after)

    while queue:
        temp = queue.popleft()

        if temp == -1:
            if queue:
                time_after += 1
                queue.append(-1)
            else:
                return
        else:
            y,x = temp
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < M and 0 <= ny < N:
                    if not new_visited[ny][nx] and board[ny][nx] != 1:
                        new_visited[ny][nx] = True
                        if ny == N-1 and nx == M-1:
                            answer = min(answer,time_after+1)
                        queue.append((ny,nx))

bfs_before()
if N == 1 and M == 1:
    print(1)
    exit()
if answer == 1e9:
    print(-1)
else:
    print(answer)

 

최단 시간을 찾는 알고리즘이 다른 사람들과 조금 다를 수도 있다.

 

다른 사람들이 보통 bfs에서 최단 경로를 찾는 방법을 보면 그래프에 +1 해가면서 찾는 것 같았는데,

얼마전 알게된 방법으로 한번 지금 갈 수 있는 모든 경로를 다 queue에 더하고 돌아와서 queue에 -1을 더해놓고 다음에 또 갈 수 있는 모든 경로를 다 queue에 더하면 몇번째 탐색인지 특정할 수 있다.  

 

어찌됬건 N과 M의 범위가 매우매우 크므로 시간초과.

 

 

두번째 접근

---

BFS를 한번만 써야하는 것을 깨달았다.

 

그렇다면 queue.appen(좌표)할 때 이미 벽을 부순 경로이면 1 벽을 부수지 않은 벽을 부술 수 있는 경로이면 0을 (좌표,x) 형식으로 경로를 특정지어주면 어떨까란 생각을 했다.

 

이때 주의해야할 점은 visited 배열도 3차원으로 만들어야한다는 것이다.

 

왜냐하면 벽을 부수고 간 경로가 최단 경로가 아닐수도 있는데, visited True로 만들어버리면 벽을 부수지 않은 경로가 가지 못하기 때문이다.

 

즉, 벽을 부수고 간 경로의 visited 배열, 벽을 부수지 않고 간 경로의 visited 배열을 따로 만들어주어야했다.

 

코드는 다음과 같다.

from collections import deque
import sys

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

board = []

for i in range(N):
    board.append(list(map(int,list(sys.stdin.readline().rstrip()))))

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

visited = [[[False,False] for _ in range(M)] for __ in range(N)]

answer = -1

def bfs():
    global answer
    queue = deque()
    queue.append((0,0,0))
    visited[0][0][0] = True
    queue.append(-1)
    time = 1
    while queue:
        temp = queue.popleft()

        if temp == -1:
            if queue:
                time += 1
                queue.append(-1)
            else:
                return
        else:
            y,x,n = temp
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < M and 0 <= ny < N:
                    if not visited[ny][nx][n]:
                        visited[ny][nx][n] = True
                        if ny == N-1 and nx == M-1:
                            answer = time+1
                            return

                        if board[ny][nx] == 1:
                            if n == 0:
                                queue.append((ny,nx,1))
                        else:
                            queue.append((ny,nx,n))

bfs()
if N == 1 and M == 1:
    print(1)
    exit()
print(answer)

 

이게 골드4라니..!!

더욱 열심히 해야겠다는 생각이 들었다..😥

 

그래도 경로를 특정지을 수 있는 좋은 방법을 하나 알게되어서 좋았다!