트리의 부모찾기 [백준 11725][JAVA][실버 2]

 

[광고 누르면 오늘의 행운 상승!!]

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

11725번: 트리의 부모 찾기

쉬운 트리 문제

1. 간선을 ArrayList를 이용하여 저장한다.

2. dfs를 이용하여 자신과 이어져 있는 노드들의 Parents 배열 인덱스를 자신으로 채워넣는다.

3. 차례대로 부모를 출력한다,.

package Study2;

import java.io.*;
import java.util.*;

class Node{
	int node;
	Node parent;
	
	Node(int node){
		this.node = node;
	}
}
public class 트리의부모찾기 {
	static ArrayList<ArrayList<Node>> graph; 
	static boolean visit[];
	static int parent[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		
		graph = new ArrayList<>();
		visit = new boolean[N];
		parent = new int[N];
		
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<>());
		}
		
		
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken())-1;
			int B = Integer.parseInt(st.nextToken())-1;
			
			graph.get(A).add(new Node(B));
			graph.get(B).add(new Node(A));
		}
		visit[0] = true;
		dfs(0);
		
		for (int i = 1; i < N; i++) {
			System.out.println(parent[i]+1);
		}
		
	}

	private static void dfs(int cur) {
		
		for(Node next : graph.get(cur)) {
			if(!visit[next.node]) {
				visit[next.node] = true;
				parent[next.node] = cur;
				dfs(next.node);
				visit[next.node] = false;
			}
		}
	}
}