⚠️ 문제
- https://www.acmicpc.net/problem/14630
🔐 풀이
이 문제는 다익스트라 알고리즘을 통해 해결할 수 있었습니다.
이 문제는 우선 문제를 올바르게 이해하는 데 어려움이 있었습니다.
문제에 제시되어 있는 예시대로 로봇의 현재 상태가 123이고 다른 상태가 222라고 한다면 비용은 (1-2)^2 + (2-2)^2 + (3-2)^2 인 2가 됩니다.
그리고 만약 각 변신 상태가 11, 33, 55인 경우 11에서 55로 변신해야할 때,
11에서 바로 55로 변신하게 되면 (1-5)^2 + (1-5)^2 인 32가 필요하지만
11에서 33을 거쳐 55로 변신하게 되면 (1-3)^2 + (1-3)^2 + (3-5)^2 + (3-5)^2 인 16이 필요하게 되어 더 작은 비용으로 변신할 수 있게 됩니다.
여기서 추가로 고려해야할 부분은
각 변신 상태가 19, 27, 28, 26에서 19에서 26으로 변신해야하는 경우 19 -> 28 -> 27 -> 26의 순서로 변신했을 때 최소가 되는, 변신 상태가 저장된 배열에서 다시 앞으로 가는 경우도 존재한다는 점입니다.
단, 19 -> 27 -> 19와 같이 다시 시작 상태로 돌아가는 경우와 19 -> 27 -> 27와 같이 똑같은 상태로의 변신은 제외해주어야 합니다.
🧑🏻💻 코드
import sys
import heapq
INF = int(1e9)
N = int(sys.stdin.readline().rstrip())
status_arr = [[] for _ in range(N)]
graph = [[] for _ in range(N)]
dist = [INF] * N
for idx in range(N):
temp = list(sys.stdin.readline().rstrip())
for n in temp:
status_arr[idx].append(int(n))
first, end = map(int, sys.stdin.readline().split())
first -= 1
end -= 1
# 변신 상태 사이의 비용 계산
def get_cost(first_arr, second_arr):
cost = 0
for idx in range(len(first_arr)):
x = first_arr[idx]
y = second_arr[idx]
cost += abs(x-y) ** 2
return cost
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
dist[start] = 0
while q:
distance, now = heapq.heappop(q)
if dist[now] < distance:
continue
# 현재 변신 상태에서 다른 변신 상태 모두 고려
for i in range(N):
# 단, 같은 상태로의 변신, 다시 시작 변신 상태로 돌아가는 경우 제외
if i == now or i == start:
continue
cost = get_cost(status_arr[now], status_arr[i]) + dist[now]
if cost < dist[i]:
dist[i] = cost
heapq.heappush(q, (cost, i))
dijkstra(first)
print(dist[end])