문제 개요
무방향 그래프(undirected graph)가 주어졌을 때, 이 그래프 내부에 홀수 길이 사이클이 존재하는지 판별하는 문제입니다.
예를 들어 인접 리스트(adjacency list)가 다음과 같이 입력된다고 가정해 보겠습니다.
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
위 그래프에는 [0, 1, 3, 4, 2], [1, 3, 4], [2, 3, 4]처럼 노드 수가 홀수인 사이클이 여러 개 존재하므로, 출력 결과는 True가 됩니다.
알고리즘 접근 방식
이 문제는 DFS(깊이 우선 탐색)를 활용해 해결할 수 있습니다. 핵심 아이디어는 현재 탐색 중인 경로(path)에서 각 노드의 깊이를 기록하고, 경로상에 이미 존재하는 노드를 다시 만났을 때 두 방문 시점의 깊이 차이가 홀수인지 확인하는 것입니다. 깊이 차이가 홀수라면 해당 구간은 곧 홀수 길이의 사이클을 의미합니다.
풀이 단계
- dfs(node, i) 함수를 정의합니다. node는 현재 노드, i는 현재 깊이를 나타냅니다.
- node가 이미 path에 있다면, (i - path[node])가 홀수일 때 True를 반환하고 그렇지 않으면 False를 반환합니다.
- node가 이미 visited 집합에 있다면 False를 반환합니다.
- node를 visited에 추가하고, path[node] := i 로 기록합니다.
- arr[node]의 각 인접 노드 c에 대해 dfs(c, i + 1)이 True라면 True를 반환합니다.
- 모든 인접 노드를 탐색한 후에는 path에서 node를 제거(백트래킹)하고 False를 반환합니다.
- 메인 루틴에서는 visited를 새로운 집합으로, path를 새로운 딕셔너리로 초기화합니다.
- 모든 노드 i에 대해 dfs(i, 0)을 호출하며, 하나라도 True를 반환하면 전체 결과는 True입니다.
- 모든 노드를 확인했는데도 홀수 사이클을 찾지 못했다면 False를 반환합니다.
파이썬 구현 예제
아래 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, arr):
def dfs(node, i):
if node in path:
return (i - path[node]) % 2 == 1
if node in visited:
return False
visited.add(node)
path[node] = i
for c in arr[node]:
if dfs(c, i + 1):
return True
del path[node]
return False
visited, path = set(), {}
for i in range(len(arr)):
if dfs(i, 0):
return True
return False
ob = Solution()
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
print(ob.solve(adj_list))
입력
[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
출력
True
추가로 알아두면 좋은 점
그래프 이론 관점에서 보면, 그래프에 홀수 길이 사이클이 존재하지 않는다는 것은 그래프가 이분 그래프(bipartite graph)라는 것과 동치입니다. 따라서 BFS를 이용해 그래프를 두 가지 색으로 칠하는 방법(2-색칠 검증)으로도 같은 문제를 해결할 수 있습니다. 위 DFS 기반 풀이는 백트래킹을 통해 현재 경로만 추적하기 때문에 직관적이며, 시간 복잡도는 노드 수 V와 간선 수 E에 대해 O(V + E) 수준으로 효율적으로 동작합니다.