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

문제

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

1707번: 이분 그래프

 

 

풀이

이분 그래프가 불가능하다 ⇒ 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같은 경우

1. 입력된 그래프 데이터를 인접 리스트로 구현한다.
2. 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다.
   • DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별한다.
   • 실행 결과가 이분 그래프가 아니면 이후 노드는 탐색하지 않는다.
   • 모든 노드로 DFS를 실행하는 이유 : 그래프의 모든 노드가 이어져 있지 않고, 여러 개의 부분 그래프로 이뤄진 케이스가 존재할 수 있기 때문이다.

 

그래프(Graph) 자료구조

그래프(Graph) 자료구조

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

void DFS(int node);
static vector<vector<int>> graph;
static vector<bool> visited;
static vector<int> group;
static bool biGraph;

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

  int K;
  cin >> K;

  for(int k = 0; k < K; k++)
  {
    int V, E;
    cin >> V >> E;

    graph.resize(V + 1);
    visited.resize(V + 1, false);
    group.resize(V + 1, 0);
	
    for(int e = 0; e < E; e++)
    {
      int u, v;
      cin >> u >> v;

      // graph 인접 리스트에 그래프 데이터 저장
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    biGraph = true;
    
    // 주어진 그래프가 하나로 연결된다는 보장이 없으므로 모든 노드에서 수행
    for(int v = 1; v <= V; v++)
    {
      if(biGraph)
      {
        DFS(v);  // 각 노드에서 DFS 실행
      }
      else
      {
        break;  // 결과가 이분 그래프가 아니면 반복 종료
      }
    }

    // 이분 그래프 여부를 정답으로 출력
    if(biGraph)
    {
      cout << "YES\n";
    }
    else
    {
      cout << "NO\n";
    }

    // 모든 변수를 다음 테스트 케이스를 위해 초기화
    for(int v = 1; v <= V; v++)
    {
      graph[v].clear();
      visited[v] = false;
      group[v] = 0;
    }
  }

  return 0;
}

// DFS 구현
void DFS(int node)
{
  visited[node] = true;  // visited 배열에 현재 노드 방문 기록

  for(int next : graph[node])
  {
    if(visited[next])
    {
      if(group[next] == group[node])
      {
        biGraph = false;  // 이미 방문한 노드가 현재 노드와 같은 집합이면 이분 그래프가 아님
      }
    }
    else
    {
      group[next] = (group[node] + 1) % 2;  // 인접한 노드는 같은 집합이 아니므로 이전 노드와 다른 집합으로 처리
      DFS(next);  // DFS 실행(재귀형태)
    }
  }
}

 

 

오답

• 사이클이 발생하여 이분 그래프가 불가능한 경우 판별

⇒ 2개의 집합을 각각 A, B로 표현하여 이분 그래프 집합 배열에 저장한다.

- DFS를 수행하여 이미 방문했던 노드에 도착했을 때, 나와 같은 집합(A or B)이면 이분 그래프 X

- 모든 노드에서 실행 → 실행 결과가 이분 그래프가 아니면 이후 노드는 탐색 X

 

• 모든 변수를 다음 테스트 케이스를 위해 초기화한다.

 

#include <iostream>
#include <vector>
using namespace std;

void DFS(int node);
static vector<vector<int>> A;
static vector<int> check;
static vector<bool> visited;
static bool IsEven;

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

  int N;
  cin >> N;
  for(int t = 0; t < N; t++)
  {
    int V, E;
    cin >> V >> E;
    A.resize(V + 1);
    visited.resize(V + 1);
    check.resize(V + 1);
    IsEven = true;

    for(int i = 0; i < E; i++)
    {
      int S, E;
      cin >> S >> E;
      // A 인접 리스트에 그래프 데이터 저장
      A[S].push_back(E);
      A[E].push_back(S);
    }
    // 주어진 그래프가 하나로 연결된다는 보장이 없으므로 모든 노드에서 수행
    for(int i = 1; i <= V; i++)
    {
      if(IsEven)
      {
        DFS(i);
      }
      else
      {
        break;	// 결과가 이분 그래프가 아니면 반복 종료
      }
    }
    // 이분 그래프 여부를 정답으로 출력
    if(IsEven)
    {
      cout << "YES" << "\n";
    }
    else
    {
      cout << "NO" << "\n";
    }
    // 모든 변수를 다음 테스트 케이스를 위해 초기화
    for(int i = 0; i <= V; i++)
    {
      A[i].clear();
      visited[i] = false;
      check[i] = 0;
    }
  }
}

// DFS 구현
void DFS(int node)
{
  visited[node] = true;	// visited 배열에 현재 노드 방문 기록

  for(int i : A[node])
  {
    // 인접한 노드는 같은 집합이 아니므로 이전 노드와 다른 집합으로 처리
    if(!visited[i])
    {
      check[i] = (check[node] + 1) % 2;
      DFS(i);	// DFS 실행(재귀 형태)
    }
    // 이미 방문한 노드가 현재 노드와 같은 집합이면 이분 그래프가 아님
    else if(check[node] == check[i])
    {
      IsEven = false;
    }
  }
}

 

[ 정답코드 예시 ]

• 2개의 집합을 각각 0, 1로 표현

⇒ check[i] = (check[node] + 1) % 2;

 

• 모든 변수를 다음 테스트 케이스를 위해 초기화

  - A[i].clear();

  - visited[i] = false;

  - check[i] = 0;