BOJ 31983 Ministarstvo
sorohue가 PS하는 블로그
문제 링크입니다.
문제 요약
$N$개의 정점으로 이루어진 토너먼트 그래프가 주어집니다. 각 간선을 적절히 색칠해, 모든 정점 $u$에 대해 한 가지 색의 간선만을 이용해서는 도달할 수 없는 정점 $v$가 존재하도록 만들려 합니다.
최소 몇 가지 색이 필요한지 구하세요.
풀이
간선 색칠에 이용할 색의 수를 $K$라고 합시다.
우선, 다른 모든 정점으로 바로 이동할 수 있는 정점이 있다면 색의 수와 관계없이 조건을 만족시킬 수 없습니다. $K=1$일 때 역시 조건을 만족시킬 수 없음이 자명합니다.
$K=2$
Claim : $K = 2$일 때, 임의의 $N$에 대해 모든 정점에 한 가지 색의 간선만을 이용해 도달할 수 있는 정점이 적어도 하나 존재합니다. 증명은 다음과 같습니다.
Claim의 반례 중 정점 수가 $N$으로 가장 적은 그래프 $G$가 있다고 가정합니다. 이는 $G$의 어떤 정점을 제거한 그래프는 모두 Claim을 만족시킨다는 의미입니다. 이는 모든 정점이 적어도 하나의 다른 정점에게, 해당 정점에서 한 가지 색 간선으로 도착할 수 없는 유일한 정점이 되어주고 있음을 의미합니다.
이로부터 출발 정점 $x$와 유일한 도착 불가 정점 $f(x)$ 사이에 일대일대응 함수 $f$가 존재함을 알 수 있습니다. $x \rarr f(x)$로 잇는 간선들을 그리면 전체는 여러 개의 사이클로 나타날 수 있는데, 우리가 고려하고 있는 건 최소 반례이므로 사이클 개수는 하나로 고정됩니다.
토너먼트 그래프에 $x \rarr f(x)$ 간선이 있다면 $f(x)$는 $x$의 도착 불가 정점이 될 수 없습니다. 따라서$f(x) \rarr x$ 방향으로 향하는 간선이 그래프에 존재해 하나의 사이클을 이루고, 이 사이클 때문에 우리의 Claim이 작동되지 않아야 합니다.
사이클을 이루는 간선의 색이 모두 같다면 모순이 발생하므로, 일반성을 잃지 않고 $f(f(x)) \rarr f(x)$와 $f(x) \rarr x$의 색이 서로 다르다고 합시다. 그런데 $f(f(x)) \rarr x$ 간선이 존재한다면 사이클을 축약할 수 있고, $x \rarr f(f(x))$ 간선이 존재한다면 $f(x) \rarr f(f(x))$ 또는 $x \rarr f(x)$로 가는 단색 경로가 존재하게 됩니다. 따라서 항상 사이클이 축약되며, 이는 결국 다른 모든 정점으로 단색 경로를 따라 이동할 수 있는 정점이 항상 존재함을 뜻합니다.
$K=3$
결론부터 말하자면, 색칠이 가능하다면 필요한 색의 최소 개수는 항상 3입니다. 어떻게 색칠해야 3가지 색으로 조건을 만족시킬 수 있을지 생각해 봅시다.
가장 먼저 해볼 수 있는 생각은 그래프의 정점을 세 그룹으로 분할해 사이클을 만드는 것입니다. 두 그룹 사이의 간선이 모두 한 방향으로만 이루어져 사이클이 만들어진다면 조건을 만족할 수 있습니다.
다만 그룹들 사이의 간선을 한 방향으로 정렬하는 것은 어려운 문제입니다. 대신, 토너먼트 그래프의 특성을 이용해 항상 사이클 중 두 간선은 방향이 정렬되도록 그룹을 나눌 수 있습니다. 이는 정점 딱 하나를 한 그룹에 넣고, 나머지 두 그룹을 각각 우리가 정한 정점에서 출발하는 방향으로 이어진 정점과, 우리가 정한 정점으로 도착하는 방향으로 이어진 정점으로 묶는 것으로 실현할 수 있습니다.
위 그림과 같이 그룹을 분할하고 간선을 색칠하면, 정점 0과 B그룹에 속한 정점은 모두 조건을 만족합니다. 이제 A그룹에 있는 모든 정점이 B그룹의 정점 중 적어도 하나에는 직접 가는 간선이 없어야 합니다. 복잡한 조건 분기를 통해 색을 결정하는 방법도 있지만, 정점 0을 진출 차수가 가장 큰 정점으로 고르면 A그룹에 있는 정점이 B그룹의 모든 정점으로 도달할 수 있으면 정점 0보다 진출차수가 커 모순이 발생하기 때문에 A그룹의 정점들 또한 조건을 만족하게 됩니다.
A그룹에서 B그룹으로 가는 간선은 어느 색으로 색칠해도 상관없으니 편한 쪽으로 구현합시다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int a[1010][1010]; int deg[1010];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int n; cin >> n; int idx = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> a[i][j];
deg[i]+=a[i][j];
}
if(deg[i] > deg[idx]) idx = i;
}
if(deg[idx] == n-1) return !(cout << -1);
cout << "3\n";
for(int i = 1; i <= n; i++, cout << '\n') for(int j = 1; j <= n; j++, cout << " ") cout << (a[i][j]?a[idx][i]==a[idx][j]?3:a[idx][i]+1:0);
}