[BOJ] 18913 Graph Coloring

www.acmicpc.net/problem/18913

18913번: Graph Coloring

 

내가 푼 문제중에 재밌던 문제의 풀이를 블로그에 올린다.

그래프의 간선들에 \(a\)~\(n\)의 색을 매길건데, 어떤 경로 \(x \to y \to z\) 에 대해 \(x \to y\) 간선의 색과 \(y \to z\) 간선의 색이 달라야 한다.

처음에는 \(2^{14}\)같은 킹리적갓심에 빠져들지만... 답은 이게 아니다.

문제 조건을 잘 생각해보면 어떤 정점으로 들어오는 간선의 색과 어떤 정점에서 나가는 색이 달라야 함을 알 수있다.

그래서 각 정점마다 들어오는 간선에 사용할 수 있는 색과 나가는 간선에 사용할 수 있는 색을 분리할 것이다.

 

어떤 정점에 숫자 x를 부여해보자.

이제 그 숫자 x를 이진수로 생각할건데, 11010이면 비트가 켜진곳이 1,2,4고 안켜진 곳이 3,5이다.

그러면 1,2,4의 색으로 정점에 들어오고 3,5의 색으로 정점에서 나간다고 생각을 할 수 있고, 

어떤 두 정점 \(x \to y\) 에 대한 간선의 색은

\(x\)에는 포함되지 않은 비트이면서 \(y\)에는 포함되있는 비트 중 하나가 될 수 있다.

그러면 이제 저 숫자를 각 정점마다 잘 부여하면 되는데, 7개의 비트는 켜저있고, 7개의 비트는 꺼져있는 숫자 \(x, y)\를 생각해보자.

그러면 서로 다른 두 수 $x, y$ 에 대해 \(x\) 에는 포함되지 않은 비트이면서 \(y\) 에는 포함되있는 비트는 적어도 하나가 있음을 알 수 있다.

14개의 비트중 7개가 커져있는 수의 개수는 \({14 \choose 7}=3432 \gt 3000\) 이므로 문제의 \(N\)제한을 충분히 넘김을 보여준다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18;
const long long mod = 1999;
const long long hashmod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,num[3005];
char a[3005][3005];
int p[15];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 2;i <= n;i++) cin >> a[i]+1;
    for(int i = 1;i <= 7;i++) p[i] = 1;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= 14;j++) {
            if(p[j]) num[i] |= (1 << j);
        }
        next_permutation(p+1,p+15);
    }
    for(int i = 2;i <= n;i++) {
        for(int j = 1;j < i;j++) {
            for(int l = 1;l <= 14;l++) {
                if(a[i][j]-'0') {
                    if((num[i] & (1 << l))&&!(num[j] & (1 << l))) {
                        cout << (char)('a'+l-1);
                        break;
                    }
                }
                else {
                    if((num[j] & (1 << l))&&!(num[i] & (1 << l))) {
                        cout << (char)('a'+l-1);
                        break;
                    }
                }
            }
        }
        cout << '\n';
    }
}