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

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

1. 문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

2. 입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

3. 출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

4. 풀이

• 이분 그래프
• BFS(DFS로도 가능)를 하면서 현재 노드와 연결된 노드에 다른 색으로 칠해준다.
  • 색 처리를 1과 -1로 해주었다.
  • 경우를 구분하지 않고 -1을 곱하면 서로 반대로 나오기 때문
  • 둘이 같은지 확인할 때도 곱해서 1인지 확인해주면 된다.
• 탐색이 모두 끝나고 서로 연결된 노드 중에 같은 색인게 있는지 찾는다.
• 같은 색인 노드가 없으면 이분 그래프이고, 있으면 이분 그래프가 아니다.

5. 처음 코드와 달라진 점

• 문제를 읽고 이분 그래프를 잘못 이해했다.
  • 그래프 간선을 하나 지웠을 때 두 개로 나눠지는지 확인하는 문제인지 알았다.
  • 며칠 전 코딩테스트에서 그런 문제가 나와서 더 그렇게 생각한 것 같다.
  • 코드를 다 뜯어 고쳤다.
• BFS 시작점을 1로 시작했는데 그래프가 서로 연결되지 않은 경우도 있어서 모든 지점에서 BFS를 해주는 걸로 수정했다.
• vector를 전역 변수로 지정하고 초기화를 안 시켜줘서 수정했다.
  • vector.clear()라는 새로운 함수를 알게 되었다.
• BFS를 할 때 이미 방문한 곳은 다시 갈 필요 없어 건너뛰는 코드를 추가했다.

6. 코드

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

using namespace std;

int v, e;
vector<int> graph[20001];
int arr[20001] ={0, };

void bfs(int start) {
  queue<int> q;
  q.push(start);
  arr[start] = 1;

  while (!q.empty()) {
    int now = q.front();
    q.pop();

    for (int i = 0; i < graph[now].size(); i++) {
      int next = graph[now][i];
      if (arr[next] != 0) continue;
      
      arr[next] = arr[now] * -1;
      q.push(next);
    }
  }
}

bool checkBinaryGraph() {
  for (int i = 1; i <= v; i++) {
    for (int j = 0; j < graph[i].size(); j++) {
      if (arr[i] * arr[graph[i][j]] == 1) return false;
    }
  }
  return true;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int k;
  cin >> k;

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

    bool isBinaryGraph = true;
    for (int i = 1; i <= v; i++) {
      if(arr[i] != 0) continue;
      bfs(i);

      if(!checkBinaryGraph()) {
        isBinaryGraph = false;
        break;
        }
    }
    
    if (isBinaryGraph) cout<<"YES\n";
    else cout<<"NO\n";

    fill_n(arr, 20001, 0);
    for (int i = 0; i <= v; i++) {
      graph[i].clear();
    }
  }
}