그래프 문제(bfs,dfs) #11725: 트리의 부모 찾기 [JAVA]

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

11725번: 트리의 부모 찾기

 

 

---

 

 

문제 접근

 

 

 

트리는 그래프의 특수한 형태로 어떤 정점의 인접한 정점은 부모 노드거나 자식 노드임.

 

이 점을 이용해서 루트 노드에서부터 그래프 탐색을 하면 부모 노드를 알 수 있다.

 

루트 노드에서부터 탐색을 하면 한 노드의 인접한 노드들 중 방문한 노드는 부모 노드이기 때문에 나머지 노드들의 부모 노드가 현재 노드이다.

 

 

 

 

 

 

 

코드

 

 

 

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 {

	static List<Integer>[] tree;
	static int[] parent;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		tree = new ArrayList[n + 1];
		parent = new int[n + 1];
		visited = new boolean[n + 1];

		for (int i = 1; i <= n; i++) {
			tree[i] = new ArrayList<>();
		}

		for (int i = 0; i < n - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			Integer a = Integer.parseInt(st.nextToken());
			Integer b = Integer.parseInt(st.nextToken());

			tree[a].add(b);
			tree[b].add(a);
		}

		dfs(1);
		for (int i = 2; i <= n; i++) {
			System.out.println(parent[i]);
		}

	}

	static void dfs(int v) {

		visited[v] = true;

		for (int i = 0; i < tree[v].size(); i++) {
			int find = tree[v].get(i);
			if (!visited[find]) {
				parent[find] = v;
				dfs(find);
			}
		}

	}

}