[백준]트리의 부모 찾기(11725번)

https://www.acmicpc.net/problem/11725
//1 문제 분석
트리의 최상위 부모를 1이라고 보았을 때, 2번부터 N번까지의 부모를 구하는 문제이다.

//2 문제 해결
주어진 입력은 한 줄에 두 수가 주어져있고 어떤 것이 부모인지는 구별되어 있지 않다. 따라서 방향이 없는 그래프로 나타내고 그래프의 관계정보는 ArrayList안의 ArrayList를 통해 저장하였다. 탐색은 1에서 부터 시작하는 dfs를 재귀를 통해 구현하였고 탐색 중 정답이 되는 부모 노드들을 배열에 저장하였다.

//3 작성 코드

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

public class FindParentsOfTree_11725 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer stz;
		StringBuilder sb = new StringBuilder();
		int[] ans = new int[N+1];
		int[] visited = new int[N+1];
		ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
		for (int i = 0 ; i<N+1 ; i++) {
			arr.add(new ArrayList<Integer>());
		}
		for (int i = 0 ; i<N-1 ;i++) {
			stz = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stz.nextToken());
			int b = Integer.parseInt(stz.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		dfs(1,arr,visited,ans);
		for (int i = 2 ; i<N+1 ; i++) {
			sb.append(ans[i]).append("\n");
		}
		System.out.println(sb);
		
	}
	static void dfs(int n, ArrayList<ArrayList<Integer>> arr, int[] visited, int[] ans) {
		for (int i = 0 ; i<arr.get(n).size(); i++) {
			int temp = arr.get(n).get(i);
			if (visited[temp]==0) {
				ans[temp]=n;
				visited[temp]=1;
				dfs(temp,arr,visited,ans);
			}
		}
	}
}

//4 시행착오
처음 코드에서는 출력을 반복문마다 System.out.println()을 사용하였더니 실행 시간이 길게 나왔다. 이를 반복문에 StringBuilder를 사용하고 System.out.println()을 한번 사용하는것으로 바꾸었더니 시간이 절반가량으로 줄어들었다.