[백준 스터디 0주차] 11725번 트리의 부모찾기 실버2 - 자바(JAVA)/ DFS

📑 문제

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

11725번: 트리의 부모 찾기

문제

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

 

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

 

 

 

 

 

 

✒️ 풀이

 각 노드의 부모라는 것이 Union-Find에서 찾는 부모가 아니고, 바로 위에 연결되어있는 노드라는 것을 뜻한다.

 1번 노드가 트리의 루트라고 하였으므로, 1번 노드를 부모로 갖는 노드들은 바로 아래 연결되어 있는 노드들이다.

 

 DFS로 1번 노드부터 해서 아래로 연결되어 있는 노드들을 쭉 탐색하면 된다!

 특정 노드에 대한 DFS 탐색에서 아래로 연결되어있고 아직 방문처리가 되지 않은 노드를 발견하면 자식노드로 처리한 후 자식노드에 대한 자식을 찾기 위해 재귀로 DFS를 다시 호출한다.

 

◻️ int[] parents[N+1]: 1번부터 N번까지 각 노드의 부모노드를 저장하는 배열

◻️ ArrayList<int>[N+1] list: 각 노드별로 연결되어있는 노드들을 저장할 ArrayList의 배열

◻️ visited[N+1]: 특정 번호의 노드를 방문처리 할 배열 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

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

//DFS
public class Main_백준_11725_트리의부모찾기_실버2 {

	static int N;
	static int[] parents;
	static boolean[] visited;
	static ArrayList<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		parents = new int[N+1];
		visited = new boolean[N+1];
		list = new ArrayList[N+1];
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			list[v1].add(v2);
			list[v2].add(v1);
		}//input
		
		dfs(1);
		
		//print
		for (int i = 2; i <= N; i++) {
			System.out.println(parents[i]);
		}
	}//end of main
	
	private static void dfs(int v) {
		visited[v]=true;
		
		for(int vertex: list[v]) {
			if(!visited[vertex]) {
				parents[vertex]=v;
				dfs(vertex);
			}
		}
	}//end of dfs
}//end of class

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨