메모리: 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)를 저장합니다. 매번 이동할 때마다 낮/밤 상태를 바꾸고, 벽을 만났을 때 낮이라면 벽을 부수고 이동하며, 밤이라면 현재 위치에서 대기하는 로직을 추가합니다.
graph에 저장합니다.visited를 False로 초기화합니다. visited[x][y][k_cnt]는 (x, y) 위치에 벽을 k_cnt개 부수고 방문했는지 여부를 나타냅니다.queue를 deque로 초기화하고 시작 위치 (0, 0)과 벽을 부순 횟수 0을 큐에 넣습니다.directions 리스트를 정의합니다.visited 배열을 갱신하고 큐에 (nx, ny, k_cnt)를 삽입합니다.visited 배열을 갱신하고 큐에 (nx, ny, k_cnt+1)를 삽입합니다. 벽을 부순 횟수를 1 증가시킵니다.wait = True로 설정합니다.night = not night).cnt += 1).visited 배열의 크기가 N * M * (K+1)이므로 공간 복잡도는 O(N * M * K)입니다. 큐의 크기 또한 최악의 경우 N * M * K가 될 수 있습니다.visited[x][y][k_cnt]는 (x, y)에 벽을 k_cnt개 부수고 방문했는지 여부를 저장합니다.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())