C++로 그래프 정점을 인접 집합으로 나눌 때 가능한 최대 분할 수 계산하기

문제 개요

그래프 G의 인접 행렬(adjacency matrix)이 주어졌다고 가정해 보겠습니다. 이때 그래프의 모든 정점을 비어 있지 않은 집합 V₁, ..., V_k로 나눌 수 있는지 확인해야 하며, 나눈다면 다음 조건을 만족해야 합니다.

모든 간선은 서로 인접한 두 집합에 속한 정점들을 연결해야 합니다.

조건을 만족하는 분할이 가능하다면, 그러한 분할에서 집합의 개수 k가 가질 수 있는 최댓값을 구해야 합니다. 만약 어떤 방식으로도 조건을 만족하는 분할이 불가능하다면 -1을 반환합니다.

예제 입력

예를 들어 입력이 다음과 같은 인접 행렬이라고 합시다.

0	1	0	1	1	0
1	0	1	0	0	1
0	1	0	1	0	0
1	0	1	0	0	0
1	0	0	0	0	0
0	1	0	0	0	0

이 경우 출력은 4가 됩니다. 즉, 정점들을 4개의 인접한 집합으로 나눌 수 있다는 의미입니다.

풀이 접근 방법

이 문제는 BFS(너비 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

각 정점을 시작점으로 삼아 BFS를 수행하고, 시작 정점의 레벨을 0으로 설정합니다.
BFS 과정에서 새로 방문하는 정점에는 현재 정점의 레벨 + 1을 부여합니다. 이 레벨 값이 곧 해당 정점이 속할 집합의 번호가 됩니다.
간선으로 연결된 두 정점의 레벨 차이가 정확히 1이 아니라면(같은 레벨이거나 2 이상 차이가 나면), 조건을 만족하는 분할이 불가능하므로 실패 플래그를 설정합니다.
모든 정점을 시작점으로 시도하면서 얻을 수 있는 최대 레벨 값을 추적하고, 성공한 경우 (최대 레벨 + 1)이 곧 가능한 최대 집합의 개수 k입니다.

이렇게 시작 정점을 바꿔 가며 BFS를 반복하는 이유는, 어느 정점에서 탐색을 시작해야 가장 많은 집합으로 나눌 수 있는지 사전에 알 수 없기 때문입니다.

알고리즘 단계

위 아이디어를 의사 코드로 정리하면 다음과 같습니다.

크기가 210인 배열 dp를 선언한다.
n := 행렬의 크기
fl := 1  (분할 가능 여부 플래그)
ans := 0
i := 0부터 시작하여 i < n이고 fl이 참인 동안 i를 1씩 증가시키며 반복:
    dp 배열 전체를 -1로 초기화
    dp[i] := 0
    큐 q를 하나 생성
    q에 i를 삽입
    q가 빌 때까지 반복:
        x := q의 맨 앞 원소
        q에서 원소 제거
        j := 0부터 j < n까지 반복:
            만약 matrix[x][j] == 1이면:
                만약 dp[j] == -1이면:
                    dp[j] := dp[x] + 1
                    q에 j를 삽입
                그렇지 않고 |dp[j] - dp[x]| != 1이면:
                    fl := 0  (분할 불가능)
    모든 j에 대해 ans := max(ans, dp[j])
만약 fl == 0이면:
    -1을 반환
그렇지 않으면:
    ans + 1을 반환

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> matrix){
   int dp[210];
   int n = matrix.size();
   int fl = 1;
   int ans = 0;
   for (int i = 0; i < n && fl; i++){
      memset(dp, -1, sizeof(dp));
      dp[i] = 0;
      queue<int> q;
      q.push(i);
      while (!q.empty()){
         int x = q.front();
         q.pop();
         for (int j = 0; j < n; j++){
            if (matrix[x][j] == 1){
               if (dp[j] == -1){
                  dp[j] = dp[x] + 1;
                  q.push(j);
               }
               else if (abs(dp[j] - dp[x]) != 1)
                  fl = 0;
            }
         }
      }
      for (int j = 0; j < n; j++)
         ans = max(ans, dp[j]);
   }
   if (fl == 0){
      return -1;
   }else{
      return ans + 1;
   }
}
int main(){
   vector<vector<int>> matrix = { { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } };
   cout << solve(matrix) << endl;
}

입력

{ { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } }

출력

동작 원리 정리

BFS를 통해 부여된 레벨 값은 시작 정점으로부터의 최단 거리를 의미합니다. 그래프의 모든 간선이 레벨 차이가 정확히 1인 정점들만 연결한다면, 같은 레벨의 정점들을 하나의 집합으로 묶는 것이 곧 조건을 만족하는 분할이 됩니다. 따라서 최대 레벨이 d라면 집합은 V₁(레벨 0), V₂(레벨 1), ..., V_d+1(레벨 d)로 총 d+1개가 되며, 이것이 답이 됩니다. 반대로 간선이 같은 레벨의 정점을 연결하거나 레벨 차이가 1이 아닌 경우가 발견되면, 어떤 시작점을 선택하더라도 조건을 만족하는 분할이 존재하지 않으므로 -1을 반환하게 됩니다.