[Python] 28707 배열 정렬

[Gold I] 배열 정렬 - 28707 

[문제 링크](https://www.acmicpc.net/problem/28707)

---

💻 문제 정의

양의 정수로 이루어진 배열이 주어졌을 때, 해당 배열을 오름차순으로 정렬하려 한다. 배열 내 원소를 서로 교환할 때 비용이 든다. 이 배열을 정렬하기 위해 $M$가지 조작을 순서와 횟수에 상관없이 조작할 수 있다고 했을 때, 최소 비용으로 오름차순 정렬된 배열을 만들어라.

💡 접근 및 설계

최단경로 알고리즘을 활용하였다. 초기의 배열 상태에서 조작이 이루어지고 난 후의 상태를 구할 때 비용이 발생함으로 [비용, 조작 이후 배열 상태] 형태로 저장할 수 있다. 최소 비용을 구하는 것이 우리의 목적이므로 우선순위 힙을 활용하여 dijkstra를 구현하여 문제를 해결할 수 있겠다 생각하였다.

✏️ 알고리즘 풀이

N = int(input())
arr = [0] + list(map(int, input().split()))
tup_arr = tuple(arr)
M = int(input())

graph = []
for _ in range(M):
    a, b, cost = map(int, input().split())
    graph.append([a, b, cost])

weight = dict() # 가중치(비용) 저장 공간

초기 세팅은 다음과 같이 정의한다.

graph : 조작은 곧 간선과 비용을 의미한다. [a] → [b] 일때, 비용 cost를 함께 저장한다.

weight : 딕셔너리를 활용하였다. 현재 배열 상태를 key로, 그때의 상태를 만들기 위한 최소 비용이 value로 들어갈 것이다. 따라서 weight[정렬된 배열]을 구하는 것이 목표이다.

# 조작 함수
def swap(tup, left, right):
    lst = list(tup)
    lst[left], lst[right] = lst[right], lst[left]
    return tuple(lst)

조작(스왑) 함수이다. 현재의 배열 상태와 위치를 바꿀 두 개의 원소가 주어지면 스왑 후 반환해주는 함수이다.

# 최단 경로 함수
def dijkstra(tup):
    queue = []
    heapq.heappush(queue, [0, tup])
    weight[tup] = 0

    while queue:
        # curr_tup : 현재 상태, cost : 현재 상태를 만들었을 때 비용
        cost, curr_tup = heapq.heappop(queue)

        for l, r, c in graph:
            # 현재 상태에서 조작한 후
            next_tup = swap(curr_tup, l, r)

            # 바뀐 상태가 존재하지 않거나 더 비싼 비용으로 조작이 이루어졌을 경우
            if weight.get(next_tup) is None or weight[next_tup] > cost + c:
                # 비용 업데이트
                weight[next_tup] = cost + c
                # 큐에 저장
                heapq.heappush(queue, [weight[next_tup], next_tup])

현재 배열의 상태와 비용을 알고 있으면, 조작 이후의 상태 및 추가된 비용을 구하게 되어 queue에 저장된다. 각 상태마다 최적의 비용이 weight에 저장되어 최종적으로 정렬된 상태에서의 비용을 구할 수 있게 된다.

🗒️ 최종 제출 코드

# 28707 배열 정렬

import heapq

INF = 10_000_000

# 조작 함수
def swap(tup, left, right):
    lst = list(tup)
    lst[left], lst[right] = lst[right], lst[left]
    return tuple(lst)

# 최단 경로 함수
def dijkstra(tup):
    queue = []
    heapq.heappush(queue, [0, tup])
    weight[tup] = 0

    while queue:
        # curr_tup : 현재 상태, cost : 현재 상태를 만들었을 때 비용
        cost, curr_tup = heapq.heappop(queue)

        for l, r, c in graph:
            # 현재 상태에서 조작한 후
            next_tup = swap(curr_tup, l, r)

            # 바뀐 상태가 존재하지 않거나 더 비싼 비용으로 조작이 이루어졌을 경우
            if weight.get(next_tup) is None or weight[next_tup] > cost + c:
                # 비용 업데이트
                weight[next_tup] = cost + c
                # 큐에 저장
                heapq.heappush(queue, [weight[next_tup], next_tup])

N = int(input())
arr = [0] + list(map(int, input().split()))
tup_arr = tuple(arr)
M = int(input())

graph = []
for _ in range(M):
    a, b, cost = map(int, input().split())
    graph.append([a, b, cost])

weight = dict() # 가중치(비용) 저장 공간

dijkstra(tup_arr)

res = tuple(sorted(arr))
print(weight[res] if res in weight else -1)

---

💭 오늘의 회고

다익스트라 최단거리 개념을 다시 한 번 다잡게 되었다. 배열의 모든 경우를 하나의 노드로 보고, 상태 변화를 간선, 그때의 비용을 가중치로 두어 최단 거리 문제로 풀어나가는 것이 핵심 아이디어였던 것 같다.