알고리즘

[백준] 14923 미로 탈출

2025년 12월 29일
74
#BOJ#Python 3#알고리즘#그래프 이론#그래프 탐색#너비 우선 탐색

[Gold III] 미로 탈출 - 14923

문제 링크

성능 요약

메모리: 129600 KB, 시간: 1248 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 설명

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

N M
Hx Hy
Ex Ey
N X M 행렬
  • 2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
  • 1 ≤ Hx, Hy, Ex, Ey ≤ 1000
  • (Hx, Hy)≠ (Ex, Ey)
  • 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

출력

D (탈출 할 수 없다면, -1을 출력한다.)

문제 풀이

문제 분석

이 문제는 홍익이가 N x M 크기의 미로에서 시작 위치(Hx, Hy)부터 탈출 위치(Ex, Ey)까지 가는 가장 짧은 경로의 거리를 찾는 문제입니다. 미로에는 빈 칸(0)과 벽(1)이 있으며, 홍익이는 마법 지팡이를 사용하여 딱 한 번 벽을 빈 칸으로 바꿀 수 있습니다. 인접한 칸으로 이동하는 데는 동일한 시간이 걸리고, 벽을 부수는 데 추가 시간이 들지 않습니다. 탈출할 수 없다면 -1을 출력해야 합니다. 입력 좌표는 1부터 시작하므로 0부터 시작하는 인덱스로 변환해야 합니다.

접근 방법

미로에서 최단 경로를 찾는 문제이므로, 너비 우선 탐색(BFS) 알고리즘이 가장 적합합니다. BFS는 각 칸을 '방문'할 때까지의 최소 거리를 보장하기 때문입니다.

이 문제의 핵심은 "지팡이를 단 한 번만 사용하여 벽을 부술 수 있다"는 제약 조건입니다. 이를 해결하기 위해 일반적인 BFS 상태 (x, y)에 추가 정보를 포함해야 합니다. 추가 정보는 '지금까지 벽을 부쉈는지 여부'입니다. 따라서 BFS의 각 상태를 (x, y, k)로 정의합니다. 여기서 x, y는 현재 위치를 나타내고, k는 벽을 부순 횟수를 나타냅니다. k는 0 (아직 벽을 부수지 않음) 또는 1 (벽을 한 번 부숨)의 값을 가질 수 있습니다.

visited 배열도 이 상태 정보를 반영해야 합니다. visited[x][y][k]는 (x, y) 위치에 k 상태로 도달한 적이 있는지 여부를 나타냅니다. 이렇게 함으로써, 같은 (x, y) 위치라도 벽을 부순 상태와 부수지 않은 상태를 다르게 처리하여 최단 경로를 탐색할 수 있습니다.

구현 설명

1. 초기 설정 및 입력 처리

  • 필요한 모듈 sys와 collections.deque를 임포트하고, input 함수를 sys.stdin.readline으로 재정의하여 입력 속도를 높입니다.
  • directions 리스트에 상하좌우 이동을 위한 튜플을 정의합니다.
  • 미로의 크기 N, M, 시작점 Hx, Hy, 끝점 Ex, Ey를 입력받습니다. 이 때, 입력으로 주어지는 1-기반 좌표를 0-기반 좌표로 변환합니다 (-1).
  • 미로의 상태를 나타내는 graph 리스트를 입력받습니다.
  • visited 배열을 [[[False, False] for _ in range(m)] for _ in range(n)] 형태로 초기화합니다. visited[x][y][0]는 (x,y)에 벽을 부수지 않고 도달했음을, visited[x][y][1]은 벽을 한 번 부수고 도달했음을 나타냅니다.
  • BFS를 위한 큐 queue를 생성하고, 시작점 (hx, hy, 0) (시작점에서는 벽을 부수지 않은 상태)을 큐에 삽입하고, visited[hx][hy][0]를 True로 표시합니다.
  • 현재 이동 거리를 저장할 변수 cnt를 0으로 초기화합니다.

2. BFS 탐색 및 거리 계산

  • while queue: 루프를 통해 큐가 비어있지 않은 동안 BFS를 진행합니다.
  • 현재 레벨 처리: for i in range(len(queue)):를 사용하여 현재 큐에 들어있는 모든 노드(현재 거리 cnt에 해당하는 모든 노드)를 한 번에 처리합니다. 이렇게 하면 BFS가 거리 1, 거리 2, ... 순서대로 탐색하여 최단 경로를 보장합니다.
  • 큐에서 현재 노드 (x, y, k)를 popleft()합니다.
  • 목표 도달 확인: 만약 현재 위치 (x, y)가 탈출 위치 (ex, ey)와 같다면, 현재까지의 이동 거리 cnt가 최단 경로이므로 cnt를 반환하고 BFS를 종료합니다.

3. 인접 칸 탐색 및 상태 전이

  • 현재 노드 (x, y)에서 상하좌우 네 방향 (dx, dy)으로 이동하여 새로운 위치 (sx, sy)를 계산합니다.
  • 경계 조건 확인: 계산된 (sx, sy)가 미로의 범위를 벗어나지 않는지 확인합니다 (0 <= sx < n and 0 <= sy < m).
  • 빈 칸인 경우 (graph[sx][sy] == 0):
    • visited[sx][sy][k]가 아직 False라면 (즉, (sx, sy)에 k 상태로 아직 도달하지 않았다면), 해당 상태 (sx, sy, k)를 큐에 추가하고 visited[sx][sy][k]를 True로 업데이트합니다. 벽을 부수지 않았으므로 k 상태는 유지됩니다.
  • 벽인 경우 (graph[sx][sy] == 1):
    • 이동하려는 칸이 벽이지만, 현재까지 벽을 부순 적이 없다면 (not k, 즉 k == 0) 그리고 (sx, sy)에 벽을 부순 상태(k=1)로 아직 도달하지 않았다면, 벽을 부수고 이동할 수 있습니다.
    • 새로운 상태 (sx, sy, 1) (벽을 부숨)을 큐에 추가하고 visited[sx][sy][1]을 True로 업데이트합니다.
  • 거리 증가: 현재 레벨의 모든 노드 탐색이 끝나면 cnt를 1 증가시켜 다음 레벨의 노드들을 탐색할 준비를 합니다.

4. 탈출 불가능 처리

  • while 루프가 모두 종료되었는데도 탈출 위치에 도달하지 못했다면, 모든 가능한 경로를 탐색했음에도 탈출구가 없다는 의미이므로 -1을 반환합니다.

⏱복잡도 분석

  • 시간 복잡도: O(N * M)

    • BFS는 각 상태(위치 (x, y)와 벽 파괴 여부 k)를 최대 한 번만 방문합니다.
    • 여기서 가능한 상태의 수는 N * M * 2 (N * M개의 칸 각각에 대해 벽을 부수지 않은 상태(k=0)와 벽을 부순 상태(k=1)가 존재)입니다.
    • 각 상태를 방문할 때마다 상하좌우 4방향을 탐색하므로, 상수는 무시하면 총 시간 복잡도는 O(N * M * 2) = O(N * M)이 됩니다.
    • N, M이 1000이므로 최대 1000 * 1000 * 2 = 2 * 10^6번의 연산이 발생하며, 이는 Python으로도 충분히 시간 내에 해결할 수 있습니다.

  • 공간 복잡도: O(N * M)

    • 미로 graph를 저장하는 데 O(N * M) 공간이 필요합니다.
    • visited 배열은 N * M * 2 크기이므로 O(N * M) 공간을 사용합니다.
    • BFS 큐에는 최악의 경우 미로의 모든 셀에 해당하는 상태가 저장될 수 있으므로 O(N * M) 공간이 필요합니다.
    • 따라서 전체 공간 복잡도는 O(N * M)입니다.

핵심 포인트

  1. 3D visited 배열 및 BFS 상태: 단 한 번의 벽 파괴 기회를 효과적으로 관리하기 위해, BFS의 각 상태를 (x, y, k) (x, y 좌표와 벽 파괴 여부 k)로 정의하고, visited[x][y][k]와 같은 3차원 배열을 사용하여 각 상태별 방문 여부를 추적하는 것이 중요합니다.
  2. 벽 파괴 로직: 벽 (graph[sx][sy] == 1)을 만났을 때, 현재 상태 k가 0 (아직 벽을 부수지 않음)이고, visited[sx][sy][1] (벽을 부수고 해당 칸에 도달하는 상태)이 False일 때만 벽을 부수고 (sx, sy, 1) 상태로 큐에 추가합니다. k가 1인 상태에서는 더 이상 벽을 부술 수 없습니다.
  3. BFS 레벨별 처리: for i in range(len(queue)): 구문을 사용하여 현재 큐에 있는 모든 노드(즉, 현재 거리 cnt에 있는 모든 노드)를 처리한 후에 cnt를 1 증가시키는 방식은 BFS가 최단 경로를 보장하는 핵심 메커니즘입니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

directions = [(1,0),(-1,0),(0,1),(0,-1)]

def BFS():
    queue = deque()
    queue.append((hx,hy,0))
    visited[hx][hy][0] = True
    cnt = 0
    while queue:
        for i in range(len(queue)):
            x,y,k = queue.popleft()
            if x == ex and y == ey:
                return cnt
            
            for dx,dy in directions:
                sx,sy = x+dx,y+dy
                if 0<=sx<n and 0<=sy<m:
                    if graph[sx][sy] == 0 and not visited[sx][sy][k]:
                        queue.append((sx,sy,k))
                        visited[sx][sy][k] = True

                    if not k and graph[sx][sy] == 1 and not visited[sx][sy][1]:
                        queue.append((sx,sy,1))
                        visited[sx][sy][1] = True
        
        cnt += 1

    return -1

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

hx,hy = map(int, input().split())
ex,ey = map(int, input().split())
hx,hy,ex,ey = hx-1,hy-1,ex-1,ey-1
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

visited = [[[False,False] for i in range(m)] for i in range(n)]

print(BFS())
댓글을 불러오는 중...