[구름] 알고리즘 먼데이 챌린지 0주차 카드 교환하기 파이썬 풀이

※사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

0주 차 챌린지

goorm

 

---

 

문제 접근

해당 문제는 구름 측에서 해설지를 제공하고있다.

그럼에도 불구하고 포스팅을 한 이유는 단순히 해설지에 파이썬 코드가 없기 때문이었다.

 

그냥 넘어가긴 조금 아쉬운 감이 있으니 해설지 내용을 간략하게 압축하여 서술하겠다.

해당 문제는 그리디로 접근이 가능하다. 그 이유는 사람의 순번이 작을수록 그 사람이 교환할 수 있는 카드 중 가장 작은 수를 선택해야 하기 때문이다.

예를 들어, 순번이 2, 5, 6 인 사람끼리 카드 교환이 가능하다고 가정하겠습니다. 그리고 세 명의 사람이 가진 카드의 수가  4, 8, 9인 경우 위에 서술한 바와 같이 사람의 순번이 작을수록 카드 숫자가 작은 것을 배치하면 다음과 같습니다. 

사람	2	5	6
카드	4	8	9
불만족지수	2	3	3

총 불만족 지수의 합은 8이 됩니다.

만약 해당 방법이 아닌 다른 방법으로 배치를 하면 어떻게 될까요?

사람	2	5	6
카드	8	4	9
불만족지수	5	1	3

총 불만족 지수는 9가 됩니다. 다르게 카드를 배분해도 절대  불만족 지수는 8 아래로 떨어지지 않습니다.

그렇기 때문에 해당 문제는 카드 교환이 가능한 사람들끼리 그룹으로 묶고(해설지에서는 해당 그룹을 컴포넌트라고 지칭했습니다.) 그룹과, 해당 그룹에 속한 사람들이 가지고 있는 카드를 오름차순으로 정렬해 배분하여 해결할 수 있습니다.

 

 

---

 

문제풀이(With Python)

import sys
from collections import deque

N, C = map(int, sys.stdin.readline().split(" "))

relation = [[] for _ in range(N+1)]

card_list = list(map(int, sys.stdin.readline().split(" ")))
# 사람의 순번이 1부터 시작하기 때문에 
# 맨 앞에 0을 추가해서 리스트가 1부터 시작하도록 설정
card_list.insert(0,0)

# 관계를 양방향으로 저장
for i in range(C):
    a,b = map(int, sys.stdin.readline().split(" "))
    relation[a].append(b)
    relation[b].append(a)

visited = [False for  _ in range(N+1)]

# 교환이 가능한 사람끼리 그룹화
def bfs(start):
    que = deque()
    component = []
    que.append(start)
    component.append(start)
    visited[start] = True
    while que:
        pos = que.popleft()
        for node in relation[pos]:
            if not visited[node]:
                que.append(node)
                component.append(node)
                visited[node] = True
    return component

# 전체 사람 그룹(컴포넌트)을 저장하는 리스트 생성 
total = []
for i in range(1, N+1):
    if not visited[i]:
        total.append(bfs(i))

dissatisfaction = 0
for people in total:
    cards = []
    # 각 그룹에 속한 사람들이 가지고있는 카드 수 선별
    for p in people:
        cards.append(card_list[p])
    # 그룹 내 사람 정렬
    people.sort()
    # 카드 수 정렬
    cards.sort()
    for person, card in zip(people, cards):
        dissatisfaction += abs(person - card)

print(dissatisfaction)