문제
루트가 1인 트리가 간선 목록으로 주어졌을 때, 각 노드의 부모 노드를 구하는 문제이다. 트리는 N개의 노드와 N-1개의 간선으로 이루어져 있으며, 부모-자식 방향 정보 없이 연결 정보만 주어진다.
입력
- 첫 번째 줄: 노드 수 N (2 이상 100,000 이하)
- 이후 N-1줄: 간선으로 연결된 두 노드 번호
출력
2번 노드부터 N번 노드까지 각 노드의 부모 노드 번호를 한 줄씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 1 6 6 3 3 5 4 1 2 4 4 7 | 4 6 1 3 1 4 |
풀이
방향 없는 트리를 인접 리스트로 구성한 뒤, 루트(1번)부터 BFS를 수행하면서 각 노드를 처음 방문할 때의 현재 노드를 부모로 기록한다.
- 각 노드를
Node객체로 만들고 인접 리스트(adj)를 양방향으로 구성한다. - 루트 1번의
root를 -1로 설정하고 큐에 삽입한다. - BFS로 탐색하면서 미방문 이웃 노드의
root를 현재 노드의 인덱스로 설정한다. - 탐색 완료 후 2번부터 N번까지
root값을 순서대로 출력한다.
핵심 아이디어: 방향 없는 그래프를 BFS로 탐색하면 자연스럽게 부모-자식 관계가 확정된다. 방문 배열을 통해 이미 처리된 노드로의 역방향 탐색을 차단하고, 처음 도달 시의 탐색 경로가 곧 트리 구조를 결정한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day50BOJ11725트리의부모 { // 11725 트리탐색
static int N;
static Node[] nodes;
static boolean[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
nodes = new Node[N + 1];
visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
nodes[i] = new Node(i);
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
nodes[a].adj.add(nodes[b]);
nodes[b].adj.add(nodes[a]);
}
System.out.println(bfs().toString());
br.close();
}
private static StringBuilder bfs() {
StringBuilder sb = new StringBuilder();
Queue<Node> q = new LinkedList<>();
nodes[1].root = -1;
q.add(nodes[1]);
while (!q.isEmpty()) {
Node now = q.poll();
for (Node no : now.adj) {
if (!visited[no.idx]) {
visited[no.idx] = true;
no.root = now.idx;
q.add(no);
}
}
}
for (int i = 2; i <= N; i++) {
sb.append(nodes[i].root).append("\n");
}
return sb;
}
static class Node {
int idx;
int root;
List<Node> adj;
public Node(int idx) {
this.idx = idx;
this.root = 0;
this.adj = new ArrayList<>();
}
}
}복잡도
- 시간: O(V + E) — 각 노드와 간선을 한 번씩 방문 (V = N, E = N-1)
- 공간: O(V + E) — 인접 리스트 및 BFS 큐