트리의 부모 찾기(백준 11725번, 자바)

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

 

 

 

[조건]

- 입력으로 노드 번호의 양방향 관계가 주어짐 

 

 

[구현]

- ArrayList 배열에 각 노드의 관계를 저장

- DFS로 탐색하면서 부모노드를 파악

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	Scanner sc=new Scanner(System.in);
	static int N;
	static ArrayList<Integer>[] arr;
	static boolean[] visit;
	static int[] num;
	
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		visit=new boolean[N+1];
		arr=new ArrayList[N+1];
		num=new int[N+1];
		
		for(int i=0;i<=N;i++) {
			arr[i]=new ArrayList<>();
		}
		
		for(int i=0;i<N-1;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			arr[b].add(a); 
			arr[a].add(b);		
		}
		dfs(1,0);
		
		for(int i=2;i<=N;i++) System.out.println(num[i]);
	}
	
	static void dfs(int x, int cnt) { //노드 번호, 방문한 노드의 개수 
		
		if(cnt==N-1) return; 
		
		for(int i=0;i<arr[x].size();i++) {
			int n=arr[x].get(i);
			if(visit[n])	continue; 
			
			visit[n]=true;
			num[n]=x;//방문하지 않은 노드의 부모 노드는 X
			dfs(n, cnt+1);
		}
	}
}