백준 11725번: 트리의 부모 찾기 [JAVA]

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

11725번: 트리의 부모 찾기

• 풀이

1. 노드의 연결 관계를 ArrayList에 입력한다.
2. 인접 노드를 탐색해서 방문하지 않은 경우(자식) 기준 노드를 부모 노드로 저장하는 함수를 작성한다.
3. 이를 루트 노드부터 시작해서 반복한다.

• 코드

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

public class Main {
	static int N; // 노드 개수
	static ArrayList<Integer> tree[]; 
	static boolean [] isVisited; // 방문 여부
	static int[] parent; // 부모 노드 저장
	
	static void findParent(int node) {
		for (int nextNode : tree[node]) { 
			if (isVisited[nextNode]==false) { // 방문하지 않은 경우 자식 노드
				isVisited[nextNode] = true; // 자식 노드 방문 체크 
				parent[nextNode] = node; // 자식 노드의 부모 노드 저장
				findParent(child); // 자식 노드 탐색
			}
		}
	}

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

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		tree = new ArrayList[N+1]; // 루트 노드가 1이라 +1
		isVisited = new boolean [N+1];
		
		parent = new int[N+1];
		
		for(int i=0; i<tree.length; i++) {
			tree[i] = new ArrayList<>(); // 각각 초기화
		}
		
		for(int i=0; i<N-1;i++) {
			// 연결 관계 입력
			st = new StringTokenizer(bf.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			tree[u].add(v);
			tree[v].add(u);
		}
		
		// 전체 노드 출력
		// for (int i=1; i<N+1;i++) System.out.println(i + " 노드 : " + tree[i]);
		
		// RootNode부터 탐색
		findParent(1);
		
		// 부모 노드 출력
		for (int i=2;i<N+1;i++) System.out.println(parent[i]);
	}

}