백준 2569 짐정리

작성일 | In |

문제 링크

알고리즘

  • 그리디
  • 순열 사이클 분할

풀이

순열 사이클 분할에 대해 파이썬으로 정리한 글이 없는 것 같아서 직접 글을 썼다.

이 문제를 풀기 전에 먼저 알게 되어서 푼 게 순열 사이클 문제다. DFS로 간단하게 풀리는 실버 3 수준의 문제인데, 짐정리 문제랑 알고리즘 태그가 똑같다. 똑같이 순열 사이클 분할 알고리즘 태그가 붙었는데 하나는 실버 3이고, 다른 하나는 플래티넘 1인 게 신기했다. 짐정리 문제를 읽고 이해하기는 쉬웠으나 처음에는 이게 먼저 풀었던 실버 3 문제의 원리랑 어떤 관련이 있는지 몰랐다. 대체 사이클이랑 뭔 상관인가 싶었다.

근데 님들 그거 앎? 잘 생각해보면 정렬되지 않은 짐, 그러니까 테스트 케이스가 10, 2, 8, 5로 주어졌을 때의 10, 2, 5의 경우가 사이클을 이룬다고 보면 이해가 된다. 결국 서로 위치를 바꿔야 하는 대상은 현재 정렬되지 않은 짐이고, 최소의 힘을 사용하기 위해서는 가장 작은 무게를 가진 짐부터 시작해야 한다.

다시, 짐의 무게가 각각 10, 2, 8, 5의 순서대로 주어졌다면 정리 대상은 10, 2, 5다. 이 경우에 먼저 2와 5의 위치를 서로 바꿔준다. 그러면 짐의 순서는 10 5 8 2가 될 것이다. 여기서 10과 2의 위치를 서로 바꾼다면 짐의 순서는 2 5 8 10으로 목표대로 정렬된다. 결과적으로 필요한 최소 힘은 (2 + 5) + (10 + 2) = 19라는 걸 알 수 있다.

그런데 짐의 무게가 각각 1, 8, 9, 7, 6의 순서대로 주어졌다면 얘기가 다르다. 정리 대상이 8, 9, 7, 6인데, 아까 방식처럼 이 사이클 내의 최소 짐을 옮겨간 결과는 답이 아니게 된다. 그러므로 케이스를 두 가지로 나눠서 생각해야 한다. 가장 작은 무게의 짐이 정렬된 상태인지 아닌지, 다시 말하자면 가장 작은 무게의 짐이 사이클에 속하는지 여부를 따져야 한다. 따라서 주어진 무게의 최솟값이 사이클에 속한다면, 그 정렬되지 않은 짐들로 구성된 사이클에서만 짐을 옮겨준다. 그러나 무게 최솟값이 사이클에 속하지 않는다면(자기 위치에 맞게 처음부터 정렬된 상태), 전체 최솟값과 사이클 내의 최솟값의 위치를 먼저 바꾼 뒤에 사이클 내의 짐들을 정리한다. 그리고 마지막으로 처음에 위치를 바꿨던 짐의 위치를 서로 바꿔준다. 결과적으로 1, 8, 9, 7, 6 테스크 케이스의 정답은 41이다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
n = int(input())

weight = []
for i in range(n):
    weight.append((int(input()), i)) # (무게, 입력 순서)
    
weight.sort()

answer = 0
visited = [0] * n

for i in range(n):
    if visited[i]:
        continue
        
    cycle = 0
    nxt = i
    
    while not visited[nxt]:
        visited[nxt] = 1
        answer += weight[nxt][0]
        cycle += 1
        nxt = weight[nxt][1]
    
    answer += min(weight[i][0] * (cycle - 2), weight[0][0] * (cycle + 1) + weight[i][0]) # 어떤 케이스에 속하는 상황인지 확인.
    
    
# weight[0][0] : 전체에서의 최솟값
    
# case 1
# 전체의 최솟값이 사이클 내에 속하는 경우. Check only non-sorted cyclic nodes.
# e.g. 10 2 8 5 -> check (10, 2, 5) -> (2 + 5) + (10 + 2) = 19

# case 2
# 전체의 최솟값이 사이클 밖에 있는 경우. First, switch position of the minimum value node in the graph with the minimum value of non-sorted cyclic nodes.
# e.g. 1 8 9 7 6 -> check (1) and (8, 9, 7, 6) -> (1 + 6) + (1 + 9) + (1 + 7) + (1 + 8) + (1 + 6) = 41

    
    
print(answer)