[11725] 트리의 부모 찾기

🔗 문제 링크

https://www.acmicpc.net/problem/11725

🔍 문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

⚠️ 제한사항

• 2 ≤ N ≤ 100,000

🗝 풀이 (언어 : Java)

DFS로 탐색해서 풀었다. 방문 체크를 해주어야 부모 쪽으로 다시 거슬러 올라가지 않는다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		List<Integer>[] edges = new ArrayList[n + 1];
		for (int i = 0; i < n + 1; i++) {
			edges[i] = new ArrayList<>();
		}
		for (int i = 0; i < n - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			edges[num1].add(num2);
			edges[num2].add(num1);
		}
		br.close();
		solution(edges);
	}

	private static void solution(List<Integer>[] edges) {
		int[] parent = new int[edges.length];
		boolean[] visited = new boolean[edges.length];
		dfs(1, edges, parent, visited);
		for (int i = 2; i < parent.length; i++) {
			System.out.println(parent[i]);
		}
	}

	private static void dfs(int start, List<Integer>[] edges, int[] parent, boolean[] visited) {
		visited[start] = true;
		for (Integer next : edges[start]) {
			if (!visited[next]) {
				parent[next] = start;
				dfs(next, edges, parent, visited);
			}
		}
	}

}