문제 소개
1부터 N까지 번호가 매겨진 N명의 사람이 있다고 가정해 보겠습니다. 우리는 모든 사람을 크기 제한 없이 두 개의 하위 그룹으로 나누려고 합니다. 단, 각 사람은 다른 사람 중 일부를 싫어할 수 있으며, 서로 싫어하는 두 사람은 같은 그룹에 배치되어서는 안 됩니다. 즉, dislikes[i] = [a, b]라는 조건이 주어지면 번호가 a와 b인 사람은 반드시 서로 다른 그룹에 속해야 합니다. 이처럼 모든 사람을 조건에 맞게 두 그룹으로 나누는 것이 가능한지 판별하는 것이 이 글의 핵심입니다.
예를 들어 입력이 N = 4이고 dislike = [[1,2],[1,3],[2,4]]라면 출력은 true입니다. 이 경우 그룹을 [1, 4]와 [2, 3]으로 나누면 모든 조건을 만족하게 됩니다.
알고리즘 접근 방식
이 문제는 그래프 이론의 이분 그래프(bipartite graph) 판별 문제와 본질적으로 동일합니다. 사람을 노드로, 서로 싫어하는 관계를 간선으로 표현하면, "인접한 두 노드는 항상 다른 그룹에 속해야 한다"는 조건 아래 전체 그래프를 두 가지 색으로 칠할 수 있는지 확인하면 됩니다. 이를 위해 깊이 우선 탐색(DFS)을 활용합니다.
풀이 단계
집합(set) 두 개를 원소로 갖는 배열 groups를 생성합니다. 이것이 최종적으로 형성될 두 그룹입니다.
노드(node), 그래프 배열(graph), 그룹 번호(x)를 매개변수로 받는 dfs() 메서드를 정의합니다.
aux := 1 - x 로 반대편 그룹의 번호를 계산합니다.
만약 groups[aux]에 이미 node가 들어 있다면 규칙 위반이므로 false를 반환합니다.
node를 groups[x]에 추가합니다.
i를 0부터 graph[node]의 크기 - 1까지 순회하면서 다음을 수행합니다.
u := graph[node][i]
groups[aux]에 u가 없으면서 dfs(u, graph, aux)의 결과가 false라면 false를 반환합니다.
모든 인접 노드를 문제없이 처리했다면 true를 반환합니다.
메인 함수에서의 처리 흐름
크기가 [N + 1]인 벡터 배열 graph를 선언합니다.
i를 0부터 dislikes의 크기 - 1까지 순회합니다.
u := dislikes[i][0], v := dislikes[i][1]
graph[u]에 v를, graph[v]에 u를 삽입하여 무방향 그래프를 완성합니다.
i를 1부터 N까지 순회합니다.
groups[0]과 groups[1] 어느 곳에도 i가 포함되어 있지 않다면(아직 방문하지 않은 연결 성분이라면)
dfs(i, graph, 0)이 false를 반환하면 전체 함수 역시 false를 반환합니다.
모든 노드가 충돌 없이 배치되었다면 true를 반환합니다.
C++ 구현 코드
아래 예제 코드를 통해 실제 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
set <int> groups[2];
bool dfs(int node, vector <int> graph[], int x){
int aux = 1 - x;
if(groups[aux].count(node)) return false;
groups[x].insert(node);
for(int i = 0; i < graph[node].size(); i++){
int u = graph[node][i];
if(!groups[aux].count(u) && !dfs(u, graph, aux)) return false;
}
return true;
}
bool possibleBipartition(int N, vector<vector<int<<& dislikes) {
vector <int> graph[N + 1];
for(int i = 0; i < dislikes.size(); i++){
int u = dislikes[i][0];
int v = dislikes[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i = 1; i <= N;i++){
if(!groups[0].count(i) && !groups[1].count(i)){
if(!dfs(i, graph, 0)) return false;
}
}
return true;
}
};
main(){
vector<vector<int>> v = {{1,2},{1,3},{2,4}};
Solution ob;
cout << (ob.possibleBipartition(4, v));
}
입력
4 [[1,2],[1,3],[2,4]]
출력
true
복잡도 분석
시간 복잡도는 O(N + E)입니다. 여기서 E는 싫어하는 관계(dislikes)의 개수를 의미하며, 각 노드와 간선을 최대 한 번씩만 방문하기 때문입니다. 공간 복잡도 또한 그래프 저장용 배열, 재귀 호출 스택, 그룹 집합을 고려하면 O(N + E)입니다.