[Python/C++] 백준 24276 - Circle

https://www.acmicpc.net/problem/24276

풀이

처음에는 4색문제인가? 하고 생각했는데 문제를 잘 읽어보면 조금 그래프가 특수한 경우라는 것을 알 수 있다.

내부에 교차점이 없다!

그러면 그래프는 여러 개의 볼록 다각형이(또는 선분이) 변을 맞대고 붙어있는 구조라는 것을 알 수 있고, 조금만 그림을 그려보면 3색으로 충분히 색칠 가능하다는 것을 알 수 있다.

 

하지만 이 문제는 애드혹, 해 구성하기 없이 그냥 그래프 탐색으로 풀 수 있다.

 

내가 생각한 첫 번째 알고리즘(틀림)은 이렇다.

 

1. 1부터 시작해서 2, 3, 4, ... 순서대로 노드를 방문한다.

2. 각 노드에서 연결된 다른 노드들의 색깔을 조사하고, 거기에 안 쓰인 가장 작은 색깔로 노드를 색칠한다.

 

몇 개의 테스트케이스를 해보면 얼핏 될 것 같은 알고리즘이다. 하지만 아래의 치명적인 반례가 있다.

 

 

내가 여기서 조금 개선한 두 번째 알고리즘(부분점수)은 이렇다.

방문 순서가 문제이다!

위 반례를 해결하려면 방문을 다음과 같이 하면 된다.

먼저 1, 2, 3을 해결한다. 1, 2, 3은 삼각형이므로 무조건 3개의 다른 색깔로 칠해진다.

그러면 6번이 확정된다! 그러니까 1, 2, 3 다음으로 6을 방문하는 방법이 없을까?

 

바로 노드들의 차수를 관리하는 것이다.

각 노드들을 방문할 때마다 연결된(그리고 아직 방문하지 않은) 노드들의 차수를 1씩 높여주고,

각 단계마다 현재 차수가 가장 높은 노드를 방문하면 되는 것이다.

여기서 가장 차수가 높은 노드를 찾기 위해서 노드 리스트를 한 번 순회해주면 여기서 $O(N)$을 잡아먹고, 최종적으로는 $O(N^2)$가 되어 부분점수를 받을 수 있다.

 

뭔가 최적화해줄 수 없을까?

 

여기서 최적화를 더한 나의 세 번째 알고리즘(AC)은 이렇다.

 

바로 우선순위 큐를 이용해주는 것이다!

우선수위 큐에서는 맨 윗 원소가 무조건 가장 큰 놈으로 유지되니까...

 

 

그러면 파이썬으로 코드를 다음과 같이 짤 수 있다.

import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
color = [0]*(N+1)
visited = [False]*(N+1)
cnt = [0]*(N+1)
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = []
color[1] = 1
nodecnt = 1
visited[1] = True
for i in graph[1]:
    cnt[i] += 1
for i in range(2, N+1):
    heapq.heappush(q, (-cnt[i], i))

while nodecnt < N:
    while True:
        _, i = heapq.heappop(q)
        if not visited[i]:
            break

    visited[i] = True
    for j in graph[i]:
        if not visited[j]:
            cnt[j] += 1
            heapq.heappush(q, (-cnt[j], j))
    nodecnt += 1

    tmp = [False]*4
    for j in graph[i]:
        tmp[color[j]] = True
    for c in range(1, 4):
        if not tmp[c]:
            color[i] = c
            break


print(max(color))
for i in range(1, N+1):
    print(color[i], end = ' ')

 

C++로는 다음과 같이 짤 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M; cin >> N >> M;
    vector<vector<int>> graph(N+1, vector<int>(0));
    int color[N+1] = {};
    bool visited[N+1] = {};
    int cnt[N+1] = {};
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    priority_queue<pair<int, int>> q;
    color[1] = 1;
    int nodecnt = 1;
    visited[1] = true;
    for (int i : graph[1]) cnt[i]++;
    for (int i = 2; i <= N; i++) {
        q.push({cnt[i], i});
    }

    while (nodecnt < N) {
        int _, i;
        while (true) {
            _ = q.top().first; i = q.top().second;
            q.pop();
            if (!visited[i]) break;
        }
        visited[i] = true;
        for (int j : graph[i]) {
            if (!visited[j]) {
                cnt[j]++;
                q.push({cnt[j], j});
            }
        }
        nodecnt++;

        bool tmp[4] = {false, false, false, false};
        for (int j : graph[i]) {
            tmp[color[j]] = true;
        }
        for (int c = 1; c <= 3; c++) {
            if (!tmp[c]) {
                color[i] = c;
                break;
            }
        }
    }

    int m = -99999;
    for (int i : color) {
        m = max(m, i);
    }
    cout << m << '\n';
    for (int i = 1; i <= N; i++) {
        cout << color[i] << ' ';
    }
}