백준 11725 트리의 부모 찾기 / JAVA

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

11725번: 트리의 부모 찾기

 

 

> 풀이(DFS)

/*
 * 백준 11725 트리의 부모찾기
 * #실버2
 * #DFS
 */

public class boj_11725 {

	static ArrayList<Integer>[] list;
	static boolean[] visited;
	static int[] answer;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		list = new ArrayList[N+1];
		visited = new boolean[N+1];
		answer = new int[N+1];
		
		// 리스트배열 속 리스트 선언
		for(int i = 0; i < N+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		// 트리그리기
		for(int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		
		DFS(1);
		
		for(int i = 2; i < answer.length; i++)
			System.out.println(answer[i]);
		
	}
	
	public static void DFS(int parent) {
		visited[parent] = true;
		for(int idx : list[parent]) { // parent 의 하위노드를 순회
			if(!visited[idx]) {       // 하위노드 방문을 안했다면
				answer[idx] = parent; // 하위노드의 부모노드로 parent 저장
				DFS(idx);
			}
		}
	}

}

 

> 풀이(BFS)