[백준] 13265번 색칠하기 (C++)

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

 

 

이 문제는 동그라미 개수, 그래프의 상관관계가 주어질때 2개의 색만을 사용하여 인접한 동그라미는 다르게 칠하여 2개의 색으로만 색칠할 수 있는지를 묻는 문제이다.

 

2개의 색만을 사용하여 그래프를 칠할 수 있는지 -> 이분그래프

 

즉 이분그래프인지 아닌지만 판별하면되는 문제이다.

 

 

따라서 dfs, bfs를 사용하여 구현할 수 있으므로 bfs를 사용하여 풀어보았다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct nutrition {
    int p;
    int f;
    int s;
    int v;
    int cost;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int T, N, M;
int visited[1001];
vector<vector<int>> v(1001);

bool bfs(int n) {        // 색깔 1, 2 사용
    queue<pii> q;
    q.push({n, 1});
    visited[n] = 1;

    while(!q.empty()) {
        int Node = q.front().first;
        int Color = q.front().second;
        q.pop();

        for(auto it : v[Node]) {
            int NextNode = it;

            if(Color == 1) {
                if(!visited[NextNode]) {        // 색깔이 칠해지지 않았을 때
                    q.push({NextNode, 2});
                    visited[NextNode] = 2;
                }
                else {
                    if(visited[NextNode] == 1) {
                        return false;
                    }
                }
            }
            else if(Color == 2) {
                if(!visited[NextNode]) {
                    q.push({NextNode, 1});
                    visited[NextNode] = 1;
                }
                else {
                    if(visited[NextNode] == 2) {
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

void solve() {
    bool check = false;
    for(int i = 1; i <= N; i++) {
        if(!visited[i]) {
            if(!bfs(i)) {
                check = true;
            }
        }
    }

    if(!check) {
        cout << "possible" << endl;
    }
    else cout << "impossible" << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N >> M;

        memset(visited, 0, sizeof(visited));
        v.clear();
        v.resize(N+1);

        for(int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }

        solve();
    }
}

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

    input();
}

 

코드를 하나씩 살펴보면

 

bool bfs(int n) {        // 색깔 1, 2 사용
    queue<pii> q;
    q.push({n, 1});
    visited[n] = 1;

    while(!q.empty()) {
        int Node = q.front().first;
        int Color = q.front().second;
        q.pop();

        for(auto it : v[Node]) {
            int NextNode = it;

            if(Color == 1) {
                if(!visited[NextNode]) {        // 색깔이 칠해지지 않았을 때
                    q.push({NextNode, 2});
                    visited[NextNode] = 2;
                }
                else {
                    if(visited[NextNode] == 1) {
                        return false;
                    }
                }
            }
            else if(Color == 2) {
                if(!visited[NextNode]) {
                    q.push({NextNode, 1});
                    visited[NextNode] = 1;
                }
                else {
                    if(visited[NextNode] == 2) {
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

 

가장 핵심코드인 bfs 함수이며 1번 노드를 큐에넣으며 visited[1]을 1로 만들어 1로 색칠했다는것 나타내기 위해서

저렇게 만들었다.

 

큐에 하나씩 빼면서 그와 인접한 노드들을 탐색하여 현재 노드의 색칠한것과 비교하여 다른색으로 칠해주며 만약 이미 색칠해져있으며 같은색으로 색칠한경우는 이분그래프가 될 수 없기 때문에 false를 반환해주었다.

 

만약 끝까지 탐색했을때 이를 위배하지 않는경우 이분그래프라고 판단하였다.