문제 이해하기
숫자 n과 2차원 배열 enemies가 주어졌다고 가정해 보겠습니다. 여기서 n은 [0, n-1] 범위로 번호가 매겨진 n명의 사람을 의미하며, enemies 배열의 각 행은 [a, b] 형태입니다. 이는 a와 b가 서로 적대적인 관계임을 나타냅니다. 우리가 해야 할 일은 n명의 사람을 두 개의 그룹으로 나누되, 적대적인 관계에 있는 두 사람이 절대 같은 그룹에 속하지 않도록 할 수 있는지 확인하는 것입니다.
예를 들어 입력이 n = 4, enemies = [[0, 3], [3, 2]]라고 해보겠습니다. 이 경우 출력은 True가 됩니다. 왜냐하면 [0, 1, 2]와 [3]이라는 두 그룹으로 나누면 적대 관계에 있는 사람들이 서로 다른 그룹에 배치되기 때문입니다.
해결 접근 방법: 이분 그래프 판별
이 문제는 그래프 이론에서 '이분 그래프(Bipartite Graph)' 판별 문제와 본질적으로 같습니다. 사람을 정점(vertex)으로, 적대 관계를 간선(edge)으로 표현한 뒤, DFS(깊이 우선 탐색)를 이용해 그래프 전체를 두 가지 색으로 교차하여 칠할 수 있는지 확인하면 됩니다.
구체적인 해결 단계는 다음과 같습니다.
graph := 비어 있는 인접 리스트(adjacency list)를 생성합니다.
enemies의 각 적대 관계 쌍 (u, v)에 대해 다음을 수행합니다.
graph[u]의 끝에 v를 추가합니다.
graph[v]의 끝에 u를 추가합니다. (양방향 그래프)
color := 새로운 맵(딕셔너리)을 생성합니다.
dfs() 함수를 정의합니다. 매개변수는 u이며, c의 초기값은 0입니다.
u가 이미 color에 존재한다면, color[u]가 c와 같을 때 true를 반환합니다.
그렇지 않으면 color[u] := c로 설정합니다.
graph[u]에 연결된 모든 v에 대해 dfs(v, c XOR 1)의 결과가 모두 참일 때 true를 반환합니다. (XOR 연산으로 인접 정점에는 반대 색을 지정)
메인 메서드에서는 0부터 n-1까지의 모든 u 중 아직 색칠되지 않은 노드에 대해 dfs(u)를 호출하고, 그 결과가 모두 참일 때 true를 반환합니다.
구현 예제
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, n, enemies):
from collections import defaultdict
graph = defaultdict(list)
for u, v in enemies:
graph[u].append(v)
graph[v].append(u)
color = {}
def dfs(u, c=0):
if u in color:
return color[u] == c
color[u] = c
return all(dfs(v, c ^ 1) for v in graph[u])
return all(dfs(u) for u in range(n) if u not in color)
ob = Solution()
n = 4
enemies = [[0, 3], [3, 2]]
print(ob.solve(n, enemies))
입력
4, [[0, 3], [3, 2]]
출력
True
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n + e)입니다. 여기서 n은 사람의 수, e는 적대 관계(간선)의 개수입니다. 각 정점과 간선을 한 번씩만 방문하기 때문에 매우 효율적입니다. 공간 복잡도 역시 인접 리스트와 색상 맵 저장을 위해 O(n + e)입니다.
만약 DFS 탐색 과정에서 이미 색칠된 정점의 색이 기대했던 색과 다르다면, 해당 그래프는 이분 그래프가 아니므로 즉시 False를 반환하게 됩니다. 이는 곧 적대 관계자들을 두 그룹으로 나누는 것이 불가능함을 의미합니다.