문제 소개
간선(edge) 리스트 형태로 표현된 그래프가 주어졌을 때, 해당 그래프가 여러 개의 트리로 구성된 집합, 즉 포레스트(forest)인지 아닌지 판별하는 문제입니다.
예를 들어 입력이 [[0, 1], [0, 2], [4, 3]]과 같다면, 각 연결 요소가 사이클 없이 트리 형태를 이루고 있으므로 출력은 True가 됩니다.
해결 접근 방법
포레스트의 핵심 조건은 사이클(순환 구조)이 존재하지 않아야 한다는 것입니다. 따라서 깊이 우선 탐색(DFS)을 수행하는 도중 이미 방문한 노드를 다시 만나게 된다면, 그래프에 사이클이 존재한다고 판단할 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- dfs(node, prev) 함수를 정의합니다.
- node가 이미 방문 목록(seen)에 있다면 False를 반환합니다. → 사이클이 발견된 경우입니다.
- node를 seen에 추가합니다.
- e[node]에 인접한 모든 노드 n에 대해, n이 직전 노드(prev)와 같지 않다면 dfs(n, node)를 재귀 호출하고, 결과가 False라면 False를 반환합니다.
- 모든 인접 노드 탐색이 끝나면 True를 반환합니다.
메인 로직에서는 다음 과정을 순서대로 수행합니다.
- 간선 정보를 저장할 빈 딕셔너리(인접 리스트) e를 생성합니다.
- 각 간선 (u, v)에 대해 e[u]에 v를, e[v]에 u를 추가하여 양방향 그래프를 구성합니다.
- 빈 집합 seen을 생성합니다.
- e의 모든 노드에 대해 아직 방문하지 않았다면 dfs(node, -1)를 호출하고, False가 반환되면 즉시 False를 반환합니다.
- 모든 노드를 사이클 없이 탐색했다면 최종적으로 True를 반환합니다.
예제 코드
아래 구현을 통해 동작 원리를 더 잘 이해할 수 있습니다.
from collections import defaultdict class Solution: def solve(self, edges): e = defaultdict(list) for t, f in edges: e[t].append(f) e[f].append(t) seen = set() def dfs(node, prev): if node in seen: return False seen.add(node) for adj in e[node]: if adj != prev: if not dfs(adj, node): return False return True for node in e: if node not in seen and not dfs(node, -1): return False return True ob = Solution() edges = [[0, 1], [0, 2], [4, 3]] print(ob.solve(edges))
입력
[[0, 1],[0, 2],[4, 3]]
출력
True
복잡도 분석
시간 복잡도: O(V + E) — 모든 정점과 간선을 각각 한 번씩만 방문하기 때문입니다.
공간 복잡도: O(V + E) — 인접 리스트, 방문 집합, 재귀 호출 스택을 위한 저장 공간이 필요합니다.