[백준/C++]#1707 - 이분 그래프

풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> a[20001];
int apart[20001];
void dfs(int node, int c) {
    apart[node] = c;
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if (apart[next] == 0) {
            dfs(next, 3-c);		// 다음 노드에 다른 값 부여
        }
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        for (int i=1; i<=n; i++) {		// a 간선 그래프를 초기화한다.
            a[i].clear();
            apart[i] = 0;
        }
        for (int i=0; i<m; i++) {
            int u,v;
            cin >> u >> v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        for (int i=1; i<=n; i++) {		// apart 값이 0이 아닐 때 모든 노드에서 부터 dfs 사용
            if (apart[i] == 0) {
                dfs(i, 1);
            }
        }
        bool isevun = true;		// 이분 그래프일 경우 true인 변수 선언
        for (int i=1; i<=n; i++) {		// 각 노드마다 연결된 모든 리스트와 값 비교
            for (int k=0; k<a[i].size(); k++) {
            	int j = a[i][k];
                if (apart[i] == apart[j]) {
                    isevun = false;
                }
            }
        }
        if (isevun)
            cout << "YES" << "\n";
        else 
            cout << "NO" << "\n";
    }
    return 0;
}

 

개념

이분 그래프

이분 그래프는 위와 같이, 각 부분으로 나눠서 각 부분끼리는 연결이 없는 그래프이다.

이를 어떤 식으로 생각해야하고, 문제를 해결해나갈지 매우 헷갈렸다..

 

이분 그래프의 특징을 생각해보면 생각보다 간단했다.

노드 자신은, 연결된 다른 노드들과 구분되어야 한다.

 

위 그림에서 예를 들자면, node 1은 node 4, node 6과 연결되어 있는데 node 1은 node 4, node 6과 구분되어야 한다.

---

vector 라이브러리에 존재하는 clear 함수가 있다.

이는 모든 원소를 제거하고 메모리만 남아있게 한다.

 

a[i].clear() 이렇게 사용되었는데, a[i]에 연결된 리스트들의 size를 0으로 만들어 버린다.

만약 a.clear() 로 사용한다면, a 배열의 size가 0이 될 것이다.

 

---

풀이

 

일단 test case을 만드는 것 외의 입력은 동일하게 받는다.

test case를 위해서 한 test가 끝나면 간선 리스트와 apart를 초기화 하는 것이 필요하다.

 

입력 뒤 모든 노드에 접근해 노드가 방문되지 않았다면 탐색한다.

 

탐색시 사용하는 함수는 기존과 조금 다르다.

그림에서는 왼쪽 영역과 오른쪽 영역으로 구분되어 있다. 이 두 영역을 값이 다른 숫자로 생각하기로 하자.

이전에 사용하고 있던 bool check[]를 int apart[]로 새로 만든다.

0이면 false이고 1, 2의 값은 서로 구별되는 영역이다.

 

예시1 : 이분 그래프 YES

node 자신과 연결된 모든 리스트(노드들)과 값이 구별된다.

 

예시2 : 이분 그래프 NO

node 자신과 연결된 모든 리스트(노드들)과 값이 구별되지 않는다.

예외가 있는 것을 확인 할 수 있다.

 

이렇게 모든 탐색이 마친뒤, 이중 for문을 사용해 한 노드에 연결된 여러 값들과 노드값을 비교한다.

 

---

+a

다른풀이(from 백준github)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector<int> a[20001];
int color[20001];
bool dfs(int node, int c) {
    color[node] = c;
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if (color[next] == 0) {
            if (dfs(next, 3-c) == false) {
                return false;
            }
        } else if (color[next] == color[node]) {
            return false;
        }
    }
    return true;
}
int main() {
    int t;
    scanf("%d\n",&t);
    while (t--) {
        int n, m;
        scanf("%d %d",&n,&m);
        for (int i=1; i<=n; i++) {
            a[i].clear();
            color[i] = 0;
        }
        for (int i=0; i<m; i++) {
            int u,v;
            scanf("%d %d",&u,&v);
            a[u].push_back(v);
            a[v].push_back(u);
        }
        bool ok = true;
        for (int i=1; i<=n; i++) {
            if (color[i] == 0) {
                if (dfs(i, 1) == false) {
                    ok = false;
                }
            }
        }
        printf("%s\n",ok ? "YES" : "NO");
    }
    return 0;
}

입력까지는 똑같고, dfs가 조금 다르다.

dfs를 bool 함수로 만들어서 탐색 내부의 계산을 늘린다.

대신, main 함수에서의 출력 계산이 줄어든 것을 확인할 수 있다.

 

※ 이 방식이 더 효율적인 것 같은데, 가시적이진 않은 것 같다.