[백준] 1707: 이분 그래프

0. 문제 주소

 

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

1707번: 이분 그래프

 

 

1. 풀이

 

BFS & DFS 카테고리를 밀다가 본 문제. 보자마자 union-find를 생각하고 코드까지 짜다가 문제를 다시 읽고 잘못 접근했다는 걸 알았다. 그 다음엔 사이클과 연관지어서 생각해봤는데, 길이가 홀수인 사이클이 존재하면 그 사이클 내에선 정점들을 조건에 맞게 이분하지 못한다는 걸 발견하고 구해볼까...하다가 더 이쁜 풀이가 있을 것 같아서 구글링을 해보았다. (별개로 아직 DFS로 사이클 구하는 코드를 짜보질 않아서 나중에 연습이 필요할 것 같다)

주로 제시하고 있는 해결방법은 다음과 같다. 각 정점들을 두 가지 색깔로 칠한다고 했을 때, BFS or DFS를 이용하여 정점들을 순회하되 "특정 정점(A라 하자)을 방문하고, 다음 정점을 방문할 때 A와 다른 종류의 색깔을 반복해서 칠해 나간다".

보고 나면 어이가 없을 정도로 쉬운데 왜 생각을 못했을까... 항상 단순한 방법부터 생각해 나가야겠다라는 걸 다시 상기시켜 준 문제.

 

 

 

2. 풀이 코드

 

* 유의할 점

1. component가 하나라는 보장이 없다 :: 순회 시작을 1번에서만 하면 안 됨

2. 초기화 :: graph 배열 조심

 

#include <bits/stdc++.h>
#define MAX 20005

using namespace std;

vector<int> graph[MAX];
int color[MAX];

void DFS(int curr){
    int next_color = color[curr]==1 ? 2 : 1;

    for (int next: graph[curr]){
        if (color[next] != 0) continue;
        color[next] = next_color;
        DFS(next);
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    int K;
    scanf("%d", &K);
    for (int i=0;i<K;i++){
        int V, E;
        scanf("%d %d", &V, &E);
        fill(color+1, color+V+1, 0);
        for (int i=1;i<=V;i++){
            graph[i].clear();
        }
        for (int i=0;i<E;i++){
            int u, v;
            scanf("%d %d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        for (int i=1;i<=V;i++){
            if (color[i] == 0) DFS(i);
        }

        int succ = true;
        for (int u=1;u<=V;u++){
            for (int v: graph[u]){
                if (color[u] == color[v]){
                    succ = false;
                    break;
                }
            }
            if (!succ) break;
        }

        if (succ) printf("YES\n");
        else printf("NO\n");

    }

    return 0;

}