[BOJ] 1707. 이분 그래프(DFS, BFS)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

우선, 이분 그래프가 무엇인지 알아야 할 것 같다.

나도 이 문제를 풀면서 알게 되었으니..

이분 그래프 : 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프.

아래 그림을 보면 바로 이해가 갈 것이다.

이분 그래프의 특징은 자신과 인접해있는 정점과 다른 특성(색 or 값)을 가지고 있다.

이 특성을 이용해서 문제를 풀면 된다.

#. BFS Code

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
bool solve()
{
    int v, e, i, j, a, b;
 
    scanf("%d %d", &v, &e);
 
    vector<vector<int> > vt(v + 1);
    vector<int> ck(v + 1);
    queue<int> q;
 
    for (i = 0; i < e; i++) {
        scanf("%d %d", &a, &b);
        vt[a].push_back(b);
        vt[b].push_back(a);
    }
 
    for (i = 1; i <= v; i++) {
        if (ck[i]) continue;
 
        q.push(i);
        ck[i] = 1;
 
        while (!q.empty()) {
            int x = q.front();
            q.pop();
 
            for (j = 0; j < vt[x].size(); j++) {
                if (ck[vt[x][j]] == 0) {
                    ck[vt[x][j]] = ~ck[x] + 1;
 
                    q.push(vt[x][j]);
                }
                else {
                    if (ck[x] + ck[vt[x][j]] != 0) {
                        return false;
                    }
                }
            }
        }
    }
 
    return true;
}
 
int main(void)
{
    int tc;
    // freopen("input.txt", "rt", stdin);
    scanf("%d", &tc);
 
    while (tc--) {
        if(solve()) printf("YES\n");
        else printf("NO\n");
    }
 
    return 0;
}

line 22~45) 모든 정점을 탐색

line 23) 이미 방문한 정점이면 pass

line 25) 방문하지 않은 정점이면 queue에 넣어주고

line 26) check!

line 28~44) queue가 빌 때까지 반복

line 29~30) queue의 제일 앞에 있는 값을 빼온다

line 32~43) 현재 정점과 연결된 정점들을 탐색

line 33) 연결된 정점이 방문하지 않은 정점이면

line 34) 현재 정점의 ~값에 1을 더해준다.

   * 여기서는 시작 노드인 1번 노드의 특성이 1이므로

     인접한 정점들은 not 1(-2) + 1 인 -1 이 된다.

반대로 not -1(0) + 1 은 1이 된다.

이렇게 특성이 1인 정점들과 -1인 정점들로 나뉘게 된다.

line 36) 체크해주고 queue에 push!

line 38~42) 연결된 정점이 이미 방문된 정점이면

line 39) 현재 정점과 특성을 비교해서 같으면 false return

(인접한 정점과 특성이 달라야 하는데 같으면 합이 0이 되어버림

 특성은 1과 -1로 나뉘어져 있으므로)

* 사실 line 33~37 은 아래 코드처럼 해도 되는데

if (ck[vt[x][j]] == 0) {
    if (ck[x] == 1) 
        ck[vt[x][j]] = -1;
    else ck[vt[x][j]] = 1;
 
    q.push(vt[x][j]);
    }
}

not(~) 연산자가 이렇게 활용될 수 있는지 몰랐다..