[BOJ/Java] 11725. 트리의 부모 찾기

[BOJ/Java] 11725. 트리의 부모 찾기

11725번: 트리의 부모 찾기

---

문제 해석

본 문제에서는 주어진 노드 수(N)를 바탕으로 트리를 구성하고, 각 노드의 부모를 찾는 작업을 수행해야 한다. 트리는 노드 간 연결 정보를 입력으로 받으며, 1번 노드를 루트 노드로 가정한다. 이 트리 정보를 활용하여 각 노드의 부모를 출력하는 것이 목표이다.

풀이 과정

제출된 코드는 너비 우선 탐색(BFS)을 활용하여 각 노드의 부모 노드를 찾는 방식으로 문제를 해결한다. 주요 절차는 다음과 같다:

1. 입력 처리 및 그래프 초기화: 노드의 수(N)를 입력받고, 인접 리스트를 이용하여 그래프를 초기화한다. 이후, 각 노드 간의 연결 정보를 입력받아 양방향으로 그래프를 구성한다.
2. BFS 실행: 1번 노드를 시작점으로 하여 BFS를 실행하며, 방문하지 않은 노드를 발견할 때마다 현재 노드를 해당 노드의 부모로 설정한다.
3. 부모 노드 출력: BFS 수행 후, 각 노드의 부모 노드를 순차적으로 출력한다.

코드

package edu.ssafy.im.BOJ.Silver.S2.No11725;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static int N; // 노드의 수
	private static ArrayList<ArrayList<Integer>> graph; // 그래프를 나타내는 인접 리스트
	private static int[] ans; // 각 노드의 부모를 저장할 배열

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		graph = new ArrayList<>();
		ans = new int[N];
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			graph.get(u).add(v);
			graph.get(v).add(u);
		}
		
		bfs(); // BFS를 이용해 부모 노드를 찾는 함수 호출
		
		for (int i = 1; i < N; i++) { // 1번 노드(루트)를 제외하고 부모 노드 출력
			sb.append(ans[i]).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	
	private static void bfs() {
		Queue<Integer> q = new ArrayDeque<>();
		boolean[] visited = new boolean[N];
		q.offer(0); // 루트 노드(1번 노드, 인덱스 0)에서 시작
		visited[0] = true;
		
		while(!q.isEmpty()) {
			int v = q.poll();
			for (int i = 0; i < graph.get(v).size(); i++) {
				int cur = graph.get(v).get(i);
				if (visited[cur]) continue; // 이미 방문한 노드는 건너뛰기
				
				visited[cur] = true;
				q.offer(cur);
				ans[cur] = v + 1; // 부모 노드 저장
			}
		}
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)이다. BFS는 각 노드를 한 번씩 방문하며, 모든 간선을 한 번씩 검토한다. 입력으로 주어진 트리는 항상 N-1개의 간선을 가지므로, BFS 실행 시간은 선형 시간에 비례한다.

느낀점

이 문제를 통해 BFS를 활용하여 트리 구조에서 노드 간 부모-자식 관계를 효과적으로 파악하는 방법을 실습할 수 있었다. 또한, 트리 구조의 기본적인 탐색 방법을 이해하고 구현하는 능력을 향상시킬 수 있는 좋은 기회가 되었다.