[Python] 백준 2206번 문제 풀이 - 벽 부수고 이동하기

문제 링크

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

아이디어

 

이 문제는 (1,1) 부터 (N,M) 까지 가는 최단 경로를 구하는 문제입니다.

0은 이동할 수 있는 곳(길)이고, 1은 이동할 수 없는 곳(벽)입니다.

여기까지만 하면 보편적인 bfs 문제라고 생각할 수 있는데, 이 문제는 벽을 1개 부술수 있는 기회가 주어집니다.

 

벽을 3개 세우는 문제에서 백트래킹을 사용해서 벽을 세우고 바이러스가 최소로 퍼지게 했기 때문에 처음에 백트래킹을 사용해서 벽을 하나씩 부셔가며 bfs를 돌려 했지만

 

입력이 1000씩 이였습니다.

bfs의 시간 복잡도는 O(V + E)로 간선의 개수는 "1000 X 1000 = 100만" 이고 Edge의 개수는 "상하좌우 4방향 = 400만" 입니다. 총 500만인데 벽의 개수가 8개만 되어도 4000만으로 2초 안에 돌 수 없겠다는 결론이 나왔습니다.

 

그래서 백트래킹으로는 시간초과가 날 것이라고 판단했고 다른 방법을 고민 했는데 떠오르지 않아 다른 블로그를 참고했습니다.

 

그래서 나온 아이디어는

"벽을 부술 수 있는 기회를 사용하지 않은 경우"와 "벽을 부술 수 있는 기회를 사용한 경우" 로 나눈 것입니다.

벽을 부술 수 있는 기회를 사용하지 않은 경우는 index를 0으로 두고 사용한 경우는 index를 1로 두고 3차원 visited 배열을 생성합니다.

기회 남아있을 때는 visited[0][y][x]로 진행하고, 기회 없을 때는 visited[1][y][x] 로 진행합니다.

 

그리고 두가지 bfs 함수 내부를 2가지 경우로 나눕니다.

"다음 이동하는 곳이 길이고 한번도 방문하지 않은 경우"와 "다음 이동하는 곳이 벽이고 벽 부수는 기회가 있는 경우"

이렇게 경우를 나누면 "다음 이동하는 곳이 벽이고 부수는 기회가 없는 경우" 는 제외됩니다.

 

다음 이동하는 곳이 길이고 방문하지 않은 경우는 그냥 이전 값에 +1 해주면서 진행합니다.

다음 이동하는 곳이 벽이고 기회가 있는 경우는 index를 1로 바꾸며 이전 값에 +1 해주면서 진행합니다.

다음 이동하는 곳이 벽이고 부수는 기회 없을 경우는 조건 안맞아서 실행이 안됩니다.

 

근데 제가 궁금했던 것은 "어떤 벽을 부수면 최단 거리가 되는지?" 였는데

이 코드에서는 벽을 만나자마자 부숴버립니다. 바로 만나는걸 부수는데 최단거리가 되나? 라는 의문이 생겨 GPT 한테 물어보니

 

BFS는 탐색할 때 "가장 짧은 거리부터 탐색"하기 때문에
벽을 바로 부수든 나중에 부수든, 가장 빨리 도착할 수 있는 경로를 자동으로 선택합니다.

라는 답변이  왔고, 반례가 생각나서 물어봤습니다.

 

이런 맵이 있을 때는, 먼저 부숴버리면 도달할 수 없는 거 아닌지 물어봤습니다.

0 1 0 0
0 1 0 1
0 0 1 0

 

그랬더니 위의 반례는 상태(벽 기회 있음, 없음)를 나누지 않고 visited 배열을 사용했을 경우 생기는 문제이고, 상태를 나누었기 때문에 벽을 부수지 않고 진행하는 경우가 있기 때문에 최적의 경로를 보장한다고 합니다.

 

저는 이해가 잘 안되서 하나씩 따라가봤습니다.

 

visited[break_cnt][y][x]

q = (break_cnt, y, x)
이고

 

위의 맵을 바탕으로 돌아보면

(break_cnt, y, x)
(0, 0 0) 을 시작으로 하면

좌표는 (0,0) 부터 시작이고 다음 이동 값은 (0,1), (1,0) 입니다.

(0,1), (1,0)을 갈때 1과 0이기 때문에 (0,1)은 부수고 (1,0)은 안부수고 진행합니다.

첫번째는 부쉈으니깐 break_cnt를 1로 바꿉니다.

 

그래서 방문 값은
visited[1][0][1] = visited[0][1][0] = 2 가 되고

큐에 들어가는 것은
(1, 0, 1), (0, 1, 0) 가 됩니다.

 

그 이후 (1, 0, 1) 을 큐에서 꺼내서 해보면
좌표가 (0, 1) 이니
(0, 2)와 (1, 1)와 (0,0) 이 가능한데
(0,0)은 방문 했으니 거르고, (1,1)은 벽을 부숴야하는데 이미 벽을 부쉈기 때문에 못가고, (0,2)를 방문하고 +1 해서
visited[1][0][2] = 3 으로 하고 큐에 (1,0,2)를 넣습니다.

 

그다음 큐에서 꺼내는 값은 (0, 1, 0)이고
(1, 0) 이고
(1, 1)과 (2, 0) (0,0)이 가능한데
(0,0)은 방문 했으니 거르고, (1, 1)의 벽을 부수고 visited[1][1][1] = 3으로 하고 큐에 (1,1,1)을 넣습니다.
(2, 0)을 방문하고 visited[0][2][0] = 3 으로 하고 큐에 (0,2,0)을 넣습니다.

이런식으로 벽을 깬 경우와 안깬 경우를 구분하고 모든 경우를 다 진행하며 BFS를 진행하기 때문에 마지막 좌표에 가장 빨리 도착한 것을 출력하면 최단 경로가 되는 것입니다.

소스코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

graph = [list(map(int, input().rstrip())) for _ in range(n)]

# visited 배열 (상태 구분(0,1) 하고 전부 0으로 초기화)
visited = [[[0] * m for _ in range(n)] for _ in range(2)]

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

def bfs(break_cnt, y, x):
    q = deque([(break_cnt, y, x)])

    # 초기 값 방문 처리 및 거리 저장
    visited[0][y][x] = 1

    while q:
        break_cnt, y, x = q.popleft()

        # 만약 마지막 좌표에 도달했다면 그 값 반환
        if y == n-1 and x == m-1:
            return visited[break_cnt][y][x]


        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]

            if (0<=ny<n) and (0<=nx<m):
                # 다음 이동하는 곳이 길이고 한번도 방문하지 않은 곳일 때
                if graph[ny][nx] == 0 and visited[break_cnt][ny][nx] == 0:
                    # 현재 상태(0 or 1)에 이전 좌표 거리 + 1 해서 방문처리 및 거리 저장
                    visited[break_cnt][ny][nx] = visited[break_cnt][y][x] + 1
                    q.append((break_cnt, ny, nx))

                # 다음이동하는 곳이 벽인데 벽 깰 기회가 남은 경우
                if graph[ny][nx] == 1 and break_cnt == 0:
                    # 벽을 부수고 상태값 1로 설정하고 안 깼던 이전 좌표의 거리 + 1 해서 저장
                    visited[1][ny][nx] = visited[0][y][x] + 1
                    q.append((1, ny, nx))

    # 마지막에 도달하지 못하고 벽에 막혔을 경우 -1 리턴
    return -1

print(bfs(0,0,0))

 

 

 

느낀 점

BFS는 최단거리를 보장한다는 것을 알고는 있었는데, 벽을 깨는 조건이 생기니깐 헷갈렸습니다.
그리고 다른 사람의 블로그를 보면서 이해하는데에도 시간이 걸렸고, 이해한 것을 바탕으로 블로그를 작성하는데는 더 많은 시간이 걸렸습니다.

근데 블로그를 작성하면서 이 문제에 대해 더 잘 알게 되었던 것 같아 뿌듯합니다.

이 아이디어는 혼자서 고민했다면 떠올리기 매우 힘들 것 같았습니다.

그래서 다양한 문제들을 풀어보며 여러 유형을 학습하여 잘 풀어내고 싶다는 생각을 하였습니다.