[백준] 13265번 색칠하기

문제: 13265번: 색칠하기

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>

using namespace std;

vector<vector<int>> circles;
vector<int> colors; // 0: 미색칠, 1: 빨강, 2:파랑

bool bfs(int start) {
    queue<int> nexts;
    nexts.push(start);
    colors[start] = 1; // 1번 정점 빨강으로 시작

    while (!nexts.empty()) {
        int cur = nexts.front();
        nexts.pop();

        for (int next : circles[cur]) {
            if (colors[next] == 0) {
                // 아직 안칠한경우
                // 현재 색과 다른 색으로 칠
                colors[next] = (colors[cur] == 1 ? 2 : 1);
                nexts.push(next);
            }
            else if (colors[next] == colors[cur]) {
                return false; // 인접한데 같은 색이면 불가!!!
            }
        }
    }
    return true; // 여기까지 온거면 색칠 가능한거임
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t-- > 0) {
        int n, m;
        cin >> n >> m;

        // 0번 인덱스 안써!!
        circles = vector<vector<int>>(n + 1);
        colors = vector<int>(n + 1);

        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            // 무방향그래프!
            circles[x].push_back(y);
            circles[y].push_back(x);
        }

        bool isPossible = true; // 색칠 가능
        for (int i = 1; i <= n; i++) {
            if (colors[i] == 0) {
                // 아직 방문하지 않은 정점이면 BFS 돌리기
                if (!bfs(i)) {
                    isPossible = false;
                    break;
                }
            }
        }
        if (isPossible) {
            cout << "possible\n";
        }
        else {
            cout << "impossible\n";
        }
    }

    return 0;
}

 

m-coloring 문제이다. 보통 2개보다 더 많은 색으로 색칠해야 하는 경우에는 백트래킹을 이용하는데 이 문제와 같이 색이 2개밖에 안 주어진 경우에는 그냥 BFS 돌리면 된다.

 

BFS 돌리다가 다음 동그라미를 색칠하려고 할 때 나랑 같은 색으로 이미 색칠된 상태라면 해당 테스트케이스는 올바르게 색칠할 수 없는 경우이다. 그래서 그냥 종료하고 impossible 출력해주면 된다.

 

m-coloring 문제는 처음 풀어봐서 신기했다.