[BOJ 11725번] 트리의 부모 찾기(JAVA)

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

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

class Main{

	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static boolean[] isVisit;
	static int[][] arr;
	static int[] parents;
	static int N;
	
	public static void main(String args[]) throws Exception {
		N=Integer.parseInt(br.readLine());
		ArrayList<Integer>[] list=new ArrayList[N+1];
		for(int i=1;i<=N;i++)	list[i]=new ArrayList<Integer>();
		for(int i=0;i<N-1;i++) {
			String s[]=br.readLine().split(" ");
			int temp1=Integer.parseInt(s[0]);
			int temp2=Integer.parseInt(s[1]);
			list[temp1].add(temp2);
			list[temp2].add(temp1);
		}
		parents=new int[N+1]; // parents[i]=j -> i의 부모는 j
		dfs(list, N, 1, 0);
		for(int i=2;i<=N;i++) {
			bw.write(parents[i]+"\n");
		}
		bw.flush();
		bw.close();
	}
	
	public static void dfs(ArrayList<Integer>[] list, int n, int start, int parent) {
		parents[start]=parent;
		for(int num:list[start]) {
			if(num!=parent) {
				dfs(list, N, num, start);
			}
		}
	}
	
}

처음에 이 문제를 함수의 재귀를 이용해서 아래와 같이 풀어보았습니다.

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

class Main{

	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static boolean[] isVisit;
	static int[][] arr;
	static int[] result;
	static int N;
	
	public static void main(String args[]) throws Exception {
		N=Integer.parseInt(br.readLine());
		isVisit=new boolean[N+1];
		arr=new int[N-1][2];
		result=new int[N+1];
		for(int i=0;i<N-1;i++) {
			String str[]=br.readLine().split(" ");
//			System.out.println(str[0]+"/"+str[1]);
			arr[i][0]=Integer.parseInt(str[0]);
			arr[i][1]=Integer.parseInt(str[1]);
//			int temp1=Integer.parseInt(s[0]);
//			int temp2=Integer.parseInt(s[1]);
//			arr[i][0]=temp1;
//			arr[i][1]=temp2;
		}
		function(1);
		for(int i=2;i<=N;i++) {
			bw.write(result[i]+"\n");
		}
		bw.flush();
		bw.close();
	}
	
	public static void function(int num) {
		if(isVisit[num]) return;
		isVisit[num]=true;
		for(int i=0;i<N-1;i++) {
			if(arr[i][0]==num) {
				function(arr[i][1]);
				result[arr[i][1]]=num;
			}
			if(arr[i][1]==num) {
				function(arr[i][0]);
				result[arr[i][0]]=num;
			}
		}
	}
	
}

결과 값은 적절히 나왔지만, 시간 초과 문제에 걸렸고, 찾아보니 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)으로 풀 수 있다는 점을 발견하였습니다.

hongku.tistory.com/253

백준/11725번 :: 트리의 부모찾기 (java 자바) - DFS, BFS 이용

위 블로그를 참고하여 맨 위의 소스 코드와 같이 dfs 코드를 구현해보았습니다.

재귀 함수를 구현했던 것과 비슷한 논리로 접근할 수 있었습니다.

아래 예제를 예시로 들어본다면, 루트 노드인 1부터 탐색을 시작합니다.

이후 1과 연결된 6과 4를 탐색하고 6과 4의 부모가 1이라고 parents 배열을 이용해 저장해줍니다.

이후 4와 연결된 2, 7을 탐색해 2, 7의 부모가 4라고 저장하고, 6과 연결된 3을 탐색해 3의 부모가 6이라고 저장해줍니다.

마지막으로 2, 7, 3을 탐색해주고 이중 3은 5와 연결되어 있으므로 5의 부모가 3임을 저장해줍니다.