본문 바로가기
Algorithm 💫/Problem Solving

[백준 1707번 이분 그래프(DFS)/ C++]

by 돼지고기맛있다 2021. 1. 22.
반응형

www.acmicpc.net/problem/1707

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수

www.acmicpc.net

 

처음에는 이분그래프가뭐지!!!! 무슨 말이 저렇게 어렵지!!!하고 있었는데 Prof.google을 통해 알게 되었다..

정말 어렵게 설명돼 있지만 결국 서로 연결돼 있는 노드끼리 다른 그룹에 속하는 그래프를 의미한다! 더 쉽게 시각적으로 이해한다면 

다음과 같다! ㅎㅎ 다음 그림을 보면 서로 연결된 노드는 다른 색을 가지고 있다 ㅎㅎ!

 

이분 그래프 예시!

 

그럼 dfs를 통해서 한 노드에 들어갈 때마다 색깔을 이전에 노드와 다르게 저장해주면 되겠지유?!

 

그러고 마지막에 나와 인접한 아이가 같은 색깔을 가지고 있는지 확인하는 작업을 진행하면 끝!

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> connection[20001];
int colored[20001];

void dfs(int v, int color)
{
    colored[v] = color;
    for (int i = 0; i < connection[v].size(); i++) {
        int to = connection[v][i];
        if (!colored[to]) {
            dfs(to, 3 - color);
        }
    }
}
bool check_color(int v_len)
{
    for (int i = 1; i <= v_len; i++) {
        for (int j = 0; j < connection[i].size(); j++) {
            int nxt = connection[i][j];
            if (colored[i] == colored[nxt])
                return false;
        }
    }
    return true;
}
int main()
{
    int t, v, e;
    cin >> t;
    while (t--) {
        cin >> v >> e;
        for (int i = 0; i <= v; i++) {
            connection[i].clear();
            colored[i] = 0;
        }

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

        for (int i = 1; i <= v; i++) {
            if (!colored[i])
                dfs(i, 1);
        }

        if (check_color(v))
            cout
                << "YES\n";
        else
            cout << "NO\n";
    }

    return 0;
}
반응형

댓글