문제
N×M 숲에서 S에서 F까지 이동할 때, 쓰레기(g)를 직접 지나는 횟수를 최소화하고, 같다면 쓰레기 옆을 지나는 횟수를 최소화하는 경로를 찾아라.
입력
첫째 줄에 N, M, 이후 N줄에 숲의 상태가 주어진다. S는 시작점, F는 도착점, g는 쓰레기, .은 빈 칸이다.
출력
쓰레기를 직접 지나는 횟수와 쓰레기 옆을 지나는 횟수를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 S.g ... ..F | 0 1 |
풀이
다익스트라 알고리즘에서 (쓰레기 직접 통과 수, 쓰레기 인접 통과 수) 튜플을 비용으로 사용한다. 쓰레기 인접 빈 칸을 전처리하여 비용을 구분한다.
- 격자를 읽으면서 쓰레기 위치를 수집하고 S, F 좌표를 기록한다
- 각 쓰레기의 4방향 인접 빈 칸을 '#'으로 표시한다 (전처리)
- S에서 시작하여 최소 힙으로 다익스트라를 수행한다 (비용: 쓰레기=+1,0, 인접=0,+1, 빈칸=0,0)
- F에 도착하면 비용 튜플을 출력한다
핵심 아이디어: 비용을 (직접 통과, 인접 통과)의 사전순 튜플로 정의하면 다익스트라가 자연스럽게 두 기준을 우선순위대로 최소화한다.
코드
import sys
import heapq
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
N, M = map(int, input().split())
L, G = list(), list()
for i in range(N):
L.append(list(input().rstrip()))
for j in range(M):
if L[i][j] == 'g':
G.append([i, j])
elif L[i][j] == 'S':
sx, sy = i, j
elif L[i][j] == 'F':
fx, fy = i, j
for x, y in G:
for i in range(4):
tx = x + dx[i]
ty = y + dy[i]
if 0 <= tx < N and 0 <= ty < M and L[tx][ty] == '.':
L[tx][ty] = '#'
Q = []
heapq.heappush(Q, (0, 0, sx, sy))
V = [[0] * (M) for _ in range(N)]
V[sx][sy] = 1
while Q:
a, b, x, y = heapq.heappop(Q)
for i in range(4):
tx = x + dx[i]
ty = y + dy[i]
if 0 <= tx < N and 0 <= ty < M and not V[tx][ty]:
V[tx][ty] = 1
if L[tx][ty] == '.':
heapq.heappush(Q, (a, b, tx, ty))
elif L[tx][ty] == '#':
heapq.heappush(Q, (a, b + 1, tx, ty))
elif L[tx][ty] == 'g':
heapq.heappush(Q, (a + 1, b, tx, ty))
else:
print(a, b)
break복잡도
- 시간: O(NM log(NM))
- 공간: O(NM)