알고리즘 (출제자 Henry)

• DFS / BFS
• 정렬

문제 해설

문제의 요구 사항을 파악해 봅시다.

• 불만족도는 어떤 사람의 번호와 그 사람이 들고 있는 카드의 번호 차이의 절댓값
• 카드 교환이 적절하게 이루어졌을 때, 불만족도 합의 최솟값 구하기

보통 난이도가 있는 문제들은 어떤 식으로 요구 사항을 구현할 수 있는지가 문제에서 명확하게 주어지지 않는 경우가 많습니다. 이 문제에서도 불만족도 합의 최솟값을 구하라고만 했지, 어떤 식으로 최솟값을 구하는지는 알려주지 않았기 때문에 문제를 푸는 게 쉽지 않을 것임을 짐작할 수 있습니다. 이런 문제일수록 관찰을 통해 문제를 하나하나 파헤치는 것이 중요합니다.

카드를 교환할 수 있는 쌍 찾기

우선 가장 먼저 할 수 있는 일은 주어진 상황을 그래프로 나타내는 것입니다. 어떤 두 정점이나 상태 간의 관계가 주어진다면, 이를 그래프로 나타내보면 좋은 정보를 얻을 수 있는 경우가 많습니다. 이 문제에서는 사람을 정점으로 하고, 친구 관계에 있는 두 사람을 간선으로 하는 그래프로 나타내줄 수 있습니다.

이제 어떤 사람들끼리 카드를 교환할 수 있을지를 관찰해 봅시다. 우선 그래프 상에서 어떤 두 사람을 연결하는 경로가 존재하기만 한다면 두 사람은 카드를 교환할 수 있습니다. 그 경로를 따라서 사람들이 연속적으로 카드를 교환해 나간다면 이 사실이 성립함을 직관적으로 알 수 있습니다. 추가로 경로 상에 있는 다른 사람들이 들고 있는 카드도 변하지 않으므로, 간선으로 직접적으로 이어져 있지 않더라도 연결만 되어 있다면 카드를 교환할 수 있습니다. 

같은 연결 컴포넌트에 있는 사람들끼리는 마음대로 카드를 교환할 수 있다는 사실을 알았으므로, 그 컴포넌트에 속한 사람들의 카드를 아무렇게나 섞은 다음 다시 나눠준다고 생각해도 무방합니다.

최적의 카드 배분 찾기

그러면 어떻게 카드를 나눠주는 것이 최적일까요? 어떤 컴포넌트에 두 명의 사람이 속해 있고, 각 사람의 번호가 라고 합시다. 그러면 와의 대소 관계에 따라 아래 여섯 가지 경우로 나뉘게 되고, 최적으로 카드를 배분해주는 경우는 검은색 점선과 같습니다. 회색 점선은 최적이 아닌 경우를 의미합니다. (그림을 클릭하면 더 선명하게 볼 수 있습니다.)

이 그림을 통해 알 수 있는 사실은, 카드를 배분하는 최적의 경우에서는 항상 점선이 교차하지 않는다는 점입니다. 이 성질은 임의의 두 쌍에 대해서 항상 성립하므로, 따라서 컴포넌트에 속한 사람의 수가 두 명보다 더 많더라도 점선이 교차하지 않는 배분 방식이 곧 최적임을 알 수 있습니다. 설명이 다소 직관적으로 이루어졌지만, Exchange Argument를 이용하면 위 직관이 성립함을 증명할 수 있습니다.

점선이 교차하지 않도록 카드를 배분하는 방법은 사람들의 번호와 카드의 번호를 정렬한 뒤, 순서대로 배분해주는 것으로 가능합니다.

이상의 내용을 정리해보면, 다음과 같은 순서로 문제를 해결할 수 있습니다.

1. 주어진 친구 관계를 그래프로 나타낸다.
2. 같은 연결 컴포넌트에 속한 사람들을 찾는다.
3. 카드 번호와 사람들의 번호를 각각 정렬한 뒤, 정렬된 순서대로 카드를 배분한다.

그래프를 탐색하는 데 , 답을 계산하는데  시간이 걸리므로 총 시간복잡도는  입니다.

주의사항

주어진 예제와 같이 연결 컴포넌트가 여러 개일 수 있습니다. 그리고 답이 32-Bit 정수 범위를 넘어갈 수 있으니, 64-Bit 정수 자료형을 이용해 문제를 해결해야 합니다.

추가로 스택 메모리 제한으로 인해, C++ 이외의 언어에서는 DFS를 이용해 연결 컴포넌트를 탐색하면 Stack Overflow가 일어날 수 있습니다. 아래 Python 정해 코드와 같이 BFS 또는 Union-Find를 이용하면 에러 없이 문제를 잘 해결 가능합니다.

코드(Python/C++)