BOJ 18913 Graph Coloring

문제 링크입니다.

문제 요약

정점이 $3\,000$개 이하인 Tournament Graph가 주어집니다. 모든 경로 $i \to j \to k$에 대해 간선 $i \to j$와 $j \to k$의 색이 서로 다르도록 각 간선을 14가지 색 중 하나로 칠하세요.

풀이

문제에서 주어진 조건을 다르게 해석합시다. 각 정점 별로 14가지 색을 들어오는 간선에 할당할 색과 나가는 간선에 할당할 색으로 구분해, 모든 $i \to j$에 대해 $i$의 나가는 색과 $j$의 들어가는 색에 적어도 하나의 공통 색을 갖도록 만드는 것과 같은 문제임을 알 수 있습니다.

정점마다, 들어가는 간선과 나가는 간선에 각각 7개의 색을 할당합시다. 이렇게 하면 간선 $i \to j$를 색칠할 수 없으려면 $i$와 $j$의 색 구분이 완전히 동일해야만 합니다. 즉 모든 정점에 서로 다른 색 구분을 할당할 수 있으면 됩니다. $\binom{14}{7} = 3\,432 > 3\,000$ 이므로 이는 실제로 가능합니다!!

코드

#include<bits/stdc++.h>
using namespace std;
vector<int> c147;
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n; cin >> n;
	for(int i=0;i<(1<<14);i++){
        int cnt=0;
        for(int j=0;j<14;j++)if((i>>j)&1)cnt++;
        if(cnt==7) c147.push_back(i);
        if(c147.size() == 3000) break;
    }
	for(int i = 1; i < n; i++){
		string s; cin >> s;
		for(int j = 0; j < i; j++){
			if(s[j] == '1'){
				for(int k = 0; k < 14; k++){
					if(!(c147[i]&(1<<k)) && (c147[j]&(1<<k))){
						cout << char('a'+k);
						break;
					}
				}
			}
			else{
				for(int k = 0; k < 14; k++){
					if((c147[i]&(1<<k)) && !(c147[j]&(1<<k))){
						cout << char('a'+k);
						break;
					}
				}
			}
		}
		cout << '\n';
	}
}