[백준-11725번 자바/java] 트리의 부모 찾기_디버깅의 눈물

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

11725번: 트리의 부모 찾기

 

 

트리의 부모 찾기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

45692

19815

14269

42.174%

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

 

 

 

체크 포인트

1. DFS(깊이 우선 탐색)를 이용하는 문제

 

2. 문제의 조건에 '노드의 개수 N (2 ≤ N ≤ 100,000)'이란 부분이 존재하여 List를 활용해 풀었다. 인접 행렬이 아닌 인접 리스트의 방식을 처음 적용해보았기 때문에 신선했다. 

 

3. 최상의 루트는 1이라는 조건이 있기 때문에, 해당 루트에 연결되어 있는 간선을 ArrayList에 담은 후, DFS 탐색을 하여 해결할 수 있었다.

 

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {

	// 노드의 개수 N
	static int N;
	
	// 지도 리스트 배열 
	static List<Integer>[] arrList;
	
	// 부모 노드를 담아주는 배열 
	static int[] parents;
	
	// 지도 방문 배열
	static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// 노드의 총 개수 
    	N = Integer.parseInt(st.nextToken());
    	
    	// 리스트 초기화 
    	arrList = new ArrayList[N+1];
    	// parents 배열 초기화 
    	parents = new int[N+1];
    	// 방문 배열 초기화 
    	visited = new boolean[N+1];
    	
    	// 노드의 수만큼 List 배열 생성 
    	for(int i=1; i<=N; i++) {
    		arrList[i] = new ArrayList<Integer>();
    	}
    	
    	// N-1개 만큼 간선 정보 입력
    	for(int i=1; i<N; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		
    		arrList[a].add(b);
    		arrList[b].add(a);
    		
    	}
    	
    	// 리스트 내용 확인 
    	/*
    	 for(int i=1; i<=N; i++) {
    		System.out.println(i + " : " +arrList[i]);
    	}
    	*/
    	
    	// DFS 탐색 시작 부분 
    	for(int i=1; i<=N; i++) {
    		// i번 노드를 방문한 적이 없다면, 
    		if(!visited[i]) {
    			DFS(i);
    		}
    	}
    	
    	// 2번 노드부터 부모노드를 순서대로 출력 
    	for(int i=2; i<=N; i++) {
    		System.out.println(parents[i]);
    	}
    }
    
    static void DFS(int x) {
    	
    	// 방문 처리 
    	visited[x] = true;
    	
    	// 노드 리스트 arrList 중에서, 방문하지 않은 간선 탐색 
    	for(int a : arrList[x]) {
    		if(!visited[a]) {
    			parents[a] = x;
    			DFS(a);
    		}
    	}
    	
    	
    }
    

} // end of Main