알고리즘 (출제자 Henry)
- DFS / BFS
- 정렬
문제 해설
문제의 요구 사항을 파악해 봅시다.
- 불만족도는 어떤 사람의 번호와 그 사람이 들고 있는 카드의 번호 차이의 절댓값
- 카드 교환이 적절하게 이루어졌을 때, 불만족도 합의 최솟값 구하기
보통 난이도가 있는 문제들은 어떤 식으로 요구 사항을 구현할 수 있는지가 문제에서 명확하게 주어지지 않는 경우가 많습니다. 이 문제에서도 불만족도 합의 최솟값을 구하라고만 했지, 어떤 식으로 최솟값을 구하는지는 알려주지 않았기 때문에 문제를 푸는 게 쉽지 않을 것임을 짐작할 수 있습니다. 이런 문제일수록 관찰을 통해 문제를 하나하나 파헤치는 것이 중요합니다.
카드를 교환할 수 있는 쌍 찾기
우선 가장 먼저 할 수 있는 일은 주어진 상황을 그래프로 나타내는 것입니다. 어떤 두 정점이나 상태 간의 관계가 주어진다면, 이를 그래프로 나타내보면 좋은 정보를 얻을 수 있는 경우가 많습니다. 이 문제에서는 사람을 정점으로 하고, 친구 관계에 있는 두 사람을 간선으로 하는 그래프로 나타내줄 수 있습니다.
이제 어떤 사람들끼리 카드를 교환할 수 있을지를 관찰해 봅시다. 우선 그래프 상에서 어떤 두 사람을 연결하는 경로가 존재하기만 한다면 두 사람은 카드를 교환할 수 있습니다. 그 경로를 따라서 사람들이 연속적으로 카드를 교환해 나간다면 이 사실이 성립함을 직관적으로 알 수 있습니다. 추가로 경로 상에 있는 다른 사람들이 들고 있는 카드도 변하지 않으므로, 간선으로 직접적으로 이어져 있지 않더라도 연결만 되어 있다면 카드를 교환할 수 있습니다.
같은 연결 컴포넌트에 있는 사람들끼리는 마음대로 카드를 교환할 수 있다는 사실을 알았으므로, 그 컴포넌트에 속한 사람들의 카드를 아무렇게나 섞은 다음 다시 나눠준다고 생각해도 무방합니다.
최적의 카드 배분 찾기
그러면 어떻게 카드를 나눠주는 것이 최적일까요? 어떤 컴포넌트에 두 명의 사람이 속해 있고, 각 사람의 번호가 라고 합시다. 그러면
와의 대소 관계에 따라 아래 여섯 가지 경우로 나뉘게 되고, 최적으로 카드를 배분해주는 경우는 검은색 점선과 같습니다. 회색 점선은 최적이 아닌 경우를 의미합니다. (그림을 클릭하면 더 선명하게 볼 수 있습니다.)
이 그림을 통해 알 수 있는 사실은, 카드를 배분하는 최적의 경우에서는 항상 점선이 교차하지 않는다는 점입니다. 이 성질은 임의의 두 쌍에 대해서 항상 성립하므로, 따라서 컴포넌트에 속한 사람의 수가 두 명보다 더 많더라도 점선이 교차하지 않는 배분 방식이 곧 최적임을 알 수 있습니다. 설명이 다소 직관적으로 이루어졌지만, Exchange Argument를 이용하면 위 직관이 성립함을 증명할 수 있습니다.
점선이 교차하지 않도록 카드를 배분하는 방법은 사람들의 번호와 카드의 번호를 정렬한 뒤, 순서대로 배분해주는 것으로 가능합니다.
이상의 내용을 정리해보면, 다음과 같은 순서로 문제를 해결할 수 있습니다.
- 주어진 친구 관계를 그래프로 나타낸다.
- 같은 연결 컴포넌트에 속한 사람들을 찾는다.
- 카드 번호와 사람들의 번호를 각각 정렬한 뒤, 정렬된 순서대로 카드를 배분한다.
그래프를 탐색하는 데 , 답을 계산하는데
시간이 걸리므로 총 시간복잡도는
입니다.
주의사항
주어진 예제와 같이 연결 컴포넌트가 여러 개일 수 있습니다. 그리고 답이 32-Bit 정수 범위를 넘어갈 수 있으니, 64-Bit 정수 자료형을 이용해 문제를 해결해야 합니다.
추가로 스택 메모리 제한으로 인해, C++ 이외의 언어에서는 DFS를 이용해 연결 컴포넌트를 탐색하면 Stack Overflow가 일어날 수 있습니다. 아래 Python 정해 코드와 같이 BFS 또는 Union-Find를 이용하면 에러 없이 문제를 잘 해결 가능합니다.
코드(Python/C++)
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
C = [0] + list(map(int, input().split()))
G = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
G[a].append(b)
G[b].append(a)
ans = 0
card, people = [], []
visit = [0 for _ in range(N + 1)]
for i in range(N + 1):
if visit[i]:
continue
card, people = [], []
visit[i] = 1
Q = deque()
Q.append(i)
while Q:
cur = Q.popleft()
card.append(C[cur])
people.append(cur)
for next in G[cur]:
if visit[next]:
continue
visit[next] = 1
Q.append(next)
card.sort()
people.sort()
for j in range(len(card)):
ans += abs(card[j] - people[j])
print(ans)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAX = 200007;
int C[MAX], V[MAX];
vector<int> G[MAX], card, people;
void DFS(int cur) {
card.push_back(C[cur]);
people.push_back(cur);
for (int next : G[cur]) {
if (V[next]) continue;
V[next] = 1;
DFS(next);
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ll N, M, ans = 0;
cin >> N >> M;
for (int i = 1; i <= N; ++i) cin >> C[i];
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for (int i = 1; i <= N; ++i) {
if (V[i]) continue;
card.clear();
people.clear();
V[i] = 1;
DFS(i);
sort(card.begin(), card.end());
sort(people.begin(), people.end());
for (int j = 0; j < card.size(); ++j) ans += abs(card[j] - people[j]);
}
cout << ans;
return 0;
}