백준 11725 - 트리의 부모 찾기

Java

11725 번 - 트리의 부모 찾기

문제

접근 방법

Tree를 구현하려다, 이진트리가 아닌거 같아 DFS로 해결하였다.

먼저 n의 개수가 최대 100,000이므로 2차원 배열은 사용하지 못하고 이중 List를 통해 tree 형태를 나타내었다.

1이 루트라고 정해져 있으므로, 1부터 시작하여 방문하는 리스트의 값들이 처음 방문하는 값이면 자식 노드이다.
만나는 자식 노드의 정보를 인덱스로 부모 인덱스를 기록하여 보모 노드들을 저장한다.

코드

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

public class Main {
	static int n, result;
	static List<List<Integer>> tree;
	static StringBuilder sb;
	static boolean[] vis;		// 노드 방문 여부를 나타냄
	static int[] parent;		// 인덱스는 자식노드이며, 부모 노드를 기록
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = stoi(br.readLine());
    	StringTokenizer stk;
    	
    	tree = new ArrayList<>();
    	
    	for(int i = 0; i <= n; i++) {
    		tree.add(new ArrayList<>());
    	}
    	int a,b;
    	for(int i = 0; i < n - 1; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		tree.get(a).add(b);
    		tree.get(b).add(a);
    	}
    	
    	sb = new StringBuilder();
    	parent = new int[n+1];
    	vis = new boolean[n+1];
    	DFS(1);
    	
    	for(int i = 2; i <= n; i++)
    		sb.append(parent[i]).append("\n");
    	
    	System.out.println(sb.toString());
    	br.close();
	}
	
	private static boolean DFS(int now) {
		vis[now] = true;	// 해당 노드는 한번 방문하면 다시 방문할 일은 없다.
		for(int next : tree.get(now)) { // 현재 노드와 이어져 있는 노드들을 탐색
			if(!vis[next]) {	// 처음 방문한 노드이면, 자식 노드이다.
				parent[next] = now;	// 자식노드를 인덱스로 부모노드를 기록
				vis[next] = true;
				DFS(next);
			}
		}
		return false;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점