[백준 18913] Graph Coloring

Constructive

1. 풀이

문제를 간단하게 설명해보자면 간선에 \(14\)가지 색들을 배분할 건데, 이때 \(i->j\;j->k\)색깔이 모두 같은 경우가 없게 배분해주어야 한다.

 

먼저 한가지 관찰할 수 있는 점이 어떤 정점에서 나가는 간선들이 사용한 색깔 집합을 S라고 하자.
 그러면 자연스럽게 이 정점에 들어오는 간선들의 색깔의 집합은 \(C−S\) 일것이다. (\(C\)는 \(14\)가지 색깔의 집합)

다음으로 관찰할 수 있는 것은 어떤 두 정점 \(U,\;V\)가 연결되어 있을 때 색깔이 배분이 안되는 상황을 생각해보자, 각 정점에서 나가는 간선들이 사용한 색깔들의 집합을 \(S_U,S_V\)라고 하고, \(C−S_U\;∩\;S_V\;=\;∅\)인 경우는 안된다.식을 정리하면 \(S_U\;⊆\;S_V\) 즉 부분집합이 되버리면 안된다는 것이다.

이 관찰들로 통해 무조건 간선들을 배분할 수 있다는 것을 알 수 있는데, \(S\)를 적당히 \(14\)의 반 \(7\)개를 배분한다하자.

 그렇다면 이 집합의 개수는 \(_{14}\mathrm{C}_{7}=3423\)개가 된다. 그렇다면 각 정점 \(3000\)개에다가
 이 \(S\)를 배분한다고 치자 충분히 배분해줄 수 있고, 길이가 같은 집합들을 배분해주면 절대로 정점들 사이중에 부분집합에 속할 리가 없으므로 무조건 정점들을 알맞게 배분해줄 수 있다.

모든 \(S\) 집합을 구해놓고, 정점들이 아무거나 배분해주고, 각 정점에서 나가는 간선의 색깔을 배분해줄 때 정점에 있는 \(S\)에 있는 원소들만 알맞게 배분해주면 색깔을 배분해줄 수 있다.

2.소스 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
 
struct Line {
    int to, idx;
};
 
vector<Line> V[3001];
vector<int> S(3001);
vector<int> inused(3001), outused(3001);
vector<int> ans(3001*3001, -1);
 
void dfs(int num, int now, int cnt, vector<int>& ans) {
    if(num == 14) {
        if (cnt == 7) ans.push_back(now);
        return;
    }
 
    dfs(num + 1, now | (1 << num), cnt + 1, ans);
    dfs(num + 1, now, cnt, ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int n; cin >> n;
    int idx = 0;
    for (int i = 1; i <= n-1; i++) {
        string str; cin >> str;
        for (int j = 1; j <= i; j++) {
            if (str[j - 1] - '0') V[i + 1].push_back({ j, idx++ });
            else V[j].push_back({ i + 1, idx++ });
        }
    }
 
    vector<int> subset;
    dfs(0, 0, 0, subset);
    for (int i = 1; i <= n; i++) S[i] = subset[i - 1];
 
    for (int pos = 1; pos <= n; pos++) {
        for (Line w : V[pos]) {
            int col = -1;
            for (int i = 0; i < 14; i++) {
                if (!(S[pos] & (1 << i)) || S[w.to] & (1 << i)) continue;
                if (!(outused[w.to] & (1 << i)) && !(inused[pos] & (1 << i))) {
                    col = i;
                    break;
                }
            }
 
            ans[w.idx] = col;
            outused[pos] |= (1 << col);
            inused[w.to] |= (1 << col);
        }
    }
 
    idx = 0;
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= i; j++)
            cout << ((char)(ans[idx++]+'a'));
        cout << "\n";
    }
 
    return 0;
}