Baekjoon 28707. 배열 정렬 / Python

28707. 배열 정렬

난이도 : 골드 1
소요 시간 : 20분
날짜 : 2024.12.28
언어 : 파이썬
알고리즘 유형 : 다익스트라, 그래프, 해시, 트리, 최단 경

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 배열 A가 주어진다.
2. 커맨드 l, r, c가 주어진다 : l과 r을 바꾼다. c의 비용이 든다.
3. 커맨드들을 이용해서 최소비용으로 정렬하라.

2. 해결 방식

1. 배열을 문자열로 저장한다.
2. 배열을 목표배열까지 가는 최소경로를 구하면 된다.
3. 다익스트라를 활용하여 최소비용을 구한다.

3. 정답 코드

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict

n = int(input())    # 배열 길이
A = ''
for num in map(int, input().split()):
    A += str(num -1) # 배열 A를 str로 받기
goal = ''.join(sorted(A))

m = int(input())    
commands = [list(map(int, input().split())) for _ in range(m)] # 명령어 배열

costs = defaultdict()
costs[A] = 0

q = [(0, A)]    # 비용, 현재 문자열

while q:
    cost, now = heappop(q)
    if costs[now] > cost:continue   # 최솟값보다 커지면 안 함
    if now == goal:continue
    for l, r, c in commands:
        next_str = now[:l-1] + now[r-1] + now[l:r-1] + now[l-1] + now[r:]
        if next_str in costs and costs[next_str] <= cost + c:continue
        costs[next_str] = cost + c
        heappush(q, (cost + c, next_str))

print(costs[goal] if goal in costs else -1)