백준 1707 이분그래프

문제설명

접근방식

이분 그래프라는 개념에 대한 이해도가 있으면 쉽게 접근할 수 있는 문제였다. 알고리즘 수업시간에 그래프 설명할 때 이름만 들어봤어서 사실 어떤 방식으로 개념을 접근하면 되는지 몰랐는데 그래프 예시와 함께 이해하면 쉽게 이해할 수 있다.

위 그림과 같은 방식으로 그래프의 정점들을 두 개의 집합으로 나눌 수 있는데 모든 정점들이 각각 인접한 정점끼리는 같은 집합에 속해있지 않는 그래프가 되어야 한다. 따라서 이 측면에서 정점 하나씩 그래프를 탐색해가면서 자신과 인접한 정점에게 자신과 다른 ID를 부여해줘야 한다. 아직 탐색이 안 되어있는 정점에는 나와 다른 ID를 그대로 부여해주면 되고 이미 탐색이 되어서 ID가 부여되어 있는 경우에는 인접한 정점의 ID를 확인해서 자신의 정점과 같은 경우에는 이분 그래프가 아닌 것을 알 수 있고 자신과 다른 경우에는 계속해서 탐색을 이어나가면 된다.

따라서 모든 그래프 내의 정점을 탐색해주고 자신과는 다른 ID를 부여해주는 작업을 수행해주면 되므로 DFS나 BFS 방식 모두 적용해 줄 수 있다. 개인적으로는 코드를 짜는게 더 편하고 본 문제에서는 크게 시간초과의 요소가 없어보이기 때문에 DFS로 구현을 해준다.

// DFS로 모든 정점 탐색하면서 인접 정점에 다른 ID 부여해주고 현재 정점과 같으면 false로 종료
void DFS(int cur, int clr){
  color[cur] = clr;
  for(int next : G[cur]){
    if(color[next] == 0){
      if(clr == 1)
        DFS(next, 2);
      else
        DFS(next, 1);
    }
    if(color[next] == color[cur]){
      flag = false;
      return;
    }
  }
}

추가로 약간의 신경써야 할 부분은 문제에서 각각의 테스트 케이스별로 처리하기를 요구했고 이를 DFS 함수에서 배열 정보를 받아야되다 보니 전역에서 선언해서 사용하는데 매번 테스트 케이스별로 새롭게 정보를 초기화해주는 작업을 해줘야 한다는 것이다.

또한 이분 그래프의 형태적인 모습 때문에 당연히 연결그래프만 이분그래프일 것이라고 판단하고 DFS를 한 정점만 잡아서 수행해도 된다고 생각했었는데 연결 그래프가 아니다하더라도 정점을 각 집합에 나눠서 묶어줄 수 있고 오히려 연결관계가 없기 때문에 더 편하게 이분그래프를 구성할 수 있는 것이었다. 따라서 반복문을 돌면서 정점 들렸는지 여부를 확인해주고 안 들렸으면 DFS를 돌려서 비연결 그래프도 확인할 수 있게 수행을 해준다.

C++ 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;


vector <vector<int>> G;
vector <int> color;
bool flag;

void DFS(int cur, int clr){
  
  color[cur] = clr;
  
  for(int next : G[cur]){
    if(color[next] == 0){
      if(clr == 1)
        DFS(next, 2);
      else
        DFS(next, 1);
    }
    if(color[next] == color[cur]){
      flag = false;
      return;
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int T;
  cin >> T;
  while(T--){
    int v, e;
    cin >> v >> e;
    
    G.resize(v+1);
    for(int i=0; i<=v; i++){
      while(!G[i].empty())
        G[i].pop_back();
    }
    
    color.resize(v+1);
    fill(color.begin(), color.end(), 0);
    
    flag = true;

    while(e--){
      int src, dst;
      cin >> src >> dst;
      G[src].push_back(dst);
      G[dst].push_back(src);
    }
    
    for(int i=1; i<=v; i++){
      if(color[i]==0)
        DFS(i, 1);
    }

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