[예시] [해설] 2. 카드 교환하기 - 알고리즘 {먼데이} 챌린지 시즌1

01 난이도 맛보기

[예시] [해설] 2. 카드 교환하기

알고리즘 (출제자 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)

py3

#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;
}

cpp

질문하기

추가 자료

추가 자료가 없습니다

여기서 새로운 학습 자료를 확인하세요!
선생님이 추가한 자료들을 바로 확인할 수 있어요.