IDEA) 트리 문제

RIAN.P·2025년 12월 1일

algorithm

ALGORITHM

목록 보기

7/8

트리 문제를 처음 접했을 때 특히 중요한 핵심 개념 + 자주 쓰이는 패턴 모음

프로그래머스) 전력망을 둘로 나누기 문제로 알아보는 트리 탐색 핵심 개념 정리

1. 트리의 성질 (Tree Properties)

노드 n개 → 간선 n-1개
사이클 없음
연결 그래프
간선 하나만 끊으면 정확히 두 개의 트리로 분리됨

2. 간선 제거 = 트리를 둘로 나누기

트리의 구조상 한 간선만 제거해도 반드시 두 그룹으로 나뉜다.

3. DFS로 서브트리 크기 세기

트리 문제에서 자주 쓰이는 패턴.
특정 노드에서 DFS를 시작하여 도달 가능한 노드를 세면 서브트리 크기를 구할 수 있다.

패턴

int dfs(node) {
	visited[node] = true;
    int count = 1;
    
    for (next : graph[node]) {
    	if (!visited[next]) {
        	count += dfs(next);
          }
    }
    return count;
}

4. 모든 간선 브루트포스 제거 전략

n ≤ 100 → 모든 간선 제거 시도해도 충분히 가능
각 간선 제거 → DFS로 서브트리 크기 계산
시간복잡도: O(n²)

5. Blocked Edge 패턴

특정 간선을 무시하면서 탐색해야 할 때 쓰는 패턴

if ((node == A && next == B)) || (node == B && next == A)) continue;

트리 문제 + 그래프 문제에서

특정 간선을 제거한 상태처럼 탐색해야 할 때

많이 사용되는 패턴

활용:

다리(bridge) 찾기
네트워크 단절
두 개의 서브 그래프로 나누기
특정 간선 무시하면서 탐색

6. 인접 리스트 그래프 구성

트리/그래프 문제의 기본 패턴
List<Integer>[] 형태로 그래프 구성.

List<Integer>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

for (int[] w: wires) {
	int v1 = w[0], v2 = w[1];
    graph[v1].add(v2);
    graph[v2].add(v1);
}