[백준] 16933 벽 부수고 이동하기 3
[Gold I] 벽 부수고 이동하기 3 - 16933
성능 요약
메모리: 500564 KB, 시간: 7852 ms
분류
그래프 이론, 그래프 탐색, 너비 우선 탐색
문제 설명
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.
이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
문제 풀이
문제 분석
N x M 크기의 맵이 주어지고, (1, 1)에서 (N, M)까지 이동하는 최단 경로를 찾는 문제입니다. 맵의 각 칸은 이동 가능한 곳(0) 또는 벽(1)으로 표현됩니다. 벽은 최대 K개까지 부술 수 있으며, 낮에만 부술 수 있습니다. 이동 시 낮과 밤이 번갈아 바뀌며, 같은 칸에 머무르는 것도 이동으로 취급합니다. 최단 경로를 출력하고, 불가능한 경우 -1을 출력합니다.
접근 방법
이 문제는 너비 우선 탐색 (BFS) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 최단 경로를 찾는 데 적합하며, 벽을 부수는 횟수와 낮/밤 상태를 고려해야 하므로 3차원 방문 배열을 사용하여 각 상태를 추적합니다. 큐에는 현재 위치 (x, y)와 벽을 부순 횟수 (k_cnt)를 저장합니다. 매번 이동할 때마다 낮/밤 상태를 바꾸고, 벽을 만났을 때 낮이라면 벽을 부수고 이동하며, 밤이라면 현재 위치에서 대기하는 로직을 추가합니다.
구현 설명
1. 입력 및 초기화
- 입력으로 맵의 크기 N, M, 부술 수 있는 벽의 최대 개수 K를 받고, 맵 정보를 2차원 리스트
graph에 저장합니다. - 방문 여부를 저장하는 3차원 배열
visited를False로 초기화합니다.visited[x][y][k_cnt]는 (x, y) 위치에 벽을 k_cnt개 부수고 방문했는지 여부를 나타냅니다. - BFS에 사용할 큐
queue를deque로 초기화하고 시작 위치 (0, 0)과 벽을 부순 횟수 0을 큐에 넣습니다. - 상하좌우 이동을 위한
directions리스트를 정의합니다.
2. BFS 탐색
- 큐가 빌 때까지 BFS를 반복합니다.
- 큐에서 현재 위치 (x, y, k_cnt)를 꺼냅니다.
- 만약 현재 위치가 목표 위치 (N-1, M-1)라면 현재까지 이동한 거리를 반환합니다.
- 상하좌우 방향으로 이동을 시도합니다.
3. 이동 조건 확인 및 큐 삽입
- 다음 위치 (nx, ny)가 맵 범위 내에 있는지 확인합니다.
- 만약 다음 위치가 이동 가능한 곳(0)이고 아직 방문하지 않았다면,
visited배열을 갱신하고 큐에 (nx, ny, k_cnt)를 삽입합니다. - 만약 다음 위치가 벽(1)이고, 아직 벽을 부술 기회가 남아있고(k_cnt < K), 아직 방문하지 않았다면, 낮/밤 상태에 따라 다른 동작을 수행합니다.
- 낮이라면,
visited배열을 갱신하고 큐에 (nx, ny, k_cnt+1)를 삽입합니다. 벽을 부순 횟수를 1 증가시킵니다. - 밤이라면, 벽을 부술 수 없으므로 현재 위치에서 대기합니다. 이 경우
wait = True로 설정합니다.
- 낮이라면,
4. 낮/밤 변경 및 이동 횟수 증가
- 한 번의 BFS 레벨 탐색이 끝나면 낮/밤 상태를 변경합니다 (
night = not night). - 이동 횟수를 1 증가시킵니다 (
cnt += 1). - 만약 큐가 비어있는데 목표 위치에 도달하지 못했다면, -1을 반환합니다.
⏱복잡도 분석
- 시간 복잡도: O(N * M * K). BFS는 최악의 경우 모든 노드를 방문하게 되며, 각 노드마다 K+1개의 벽을 부순 상태를 고려해야 합니다. 따라서 N * M * (K+1)이지만, K는 최대 10이므로 N * M * K로 표현할 수 있습니다.
- 공간 복잡도: O(N * M * K).
visited배열의 크기가 N * M * (K+1)이므로 공간 복잡도는 O(N * M * K)입니다. 큐의 크기 또한 최악의 경우 N * M * K가 될 수 있습니다.
핵심 포인트
- 3차원 방문 배열: 벽을 부순 횟수와 현재 위치를 함께 고려하기 위해 3차원 방문 배열을 사용해야 합니다.
visited[x][y][k_cnt]는 (x, y)에 벽을 k_cnt개 부수고 방문했는지 여부를 저장합니다. - 낮/밤 상태 관리: 이동할 때마다 낮/밤 상태를 번갈아 변경하고, 밤에는 벽을 부술 수 없으므로 현재 위치에서 대기하는 로직을 구현해야 합니다.
- 벽 부수기 횟수 제한: 벽을 부술 수 있는 횟수가 K로 제한되어 있으므로, 벽을 부술 때마다 K를 감소시키고, K가 0이 되면 더 이상 벽을 부술 수 없도록 처리해야 합니다.
풀이 코드
import sys
from itertools import combinations
from collections import deque
input = sys.stdin.readline
n,m,k= map(int,input().split())
graph= []
for i in range(n):
graph.append(list(map(int, input().strip())))
directions = [(1,0),(-1,0),(0,1),(0,-1)]
visited = [[[False for _ in range(k+1)] for _ in range(m)] for _ in range(n)]
def BFS():
queue = deque()
queue.append((0,0,0))
visited[0][0][0] = True
night = False
cnt = 1
while queue:
for i in range(len(queue)):
x,y,k_cnt = queue.popleft()
wait = False
if x == n-1 and y == m-1:
return cnt
for dx,dy in directions:
nx, ny = x+dx, y+dy
if 0<=nx<n and 0<=ny<m:
if graph[nx][ny] == 0 and not visited[nx][ny][k_cnt]:
visited[nx][ny][k_cnt] = True
queue.append((nx, ny, k_cnt))
elif graph[nx][ny] == 1 and k_cnt < k:
if not night and not visited[nx][ny][k_cnt+1]:
visited[nx][ny][k_cnt+1] = True
queue.append((nx, ny, k_cnt+1))
if night:
wait = True
if wait:
queue.append((x,y,k_cnt))
night = not night
cnt += 1
return -1
print(BFS())