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

문제 출처 - Baekjoon Online Judge

문제는 여기

11725번: 트리의 부모 찾기

[문제] 

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

[입력]

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

[출력]

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

 

 

---

[풀이]

1. ArrayList의 배열을 만들어준다.

2. 값을 입력받아준다.

3. 배열 형태로 선언된 리스트에 연결관계를 표시하기 위해 입력받은 x, y에 서로 다른 값을 추가해준다.

4. 방문 처리가 되지 않은 곳을 dfs 탐색을 하여 부모 노드의 값을 저장해준다.

5. 2번 노드부터 출력을 해야 하니 2부터 출력을 해준다.

[접근]

1. 인접 배열로 문제를 해결하려고 했다가 더 좋은 방법이 없을까 해서 검색을 해보니 ArrayList의 배열 형태로 문제를 해결한 것을 보아 참고하여 문제를 해결하였다.

2. dfs 탐색을 하여 부모 노드의 값을 저장해준다.

3. 모든 탐색이 끝나고 나면 출력해준다.

[코드]

package BOJ_silver;

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

public class Main_S2_11725 {
	static int n ;
    static ArrayList<Integer>[] list; // 리스트의 배열
    static int[] parents; // 부모노드
    static boolean[] visited; // 방문처리


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 초기화
        list = new ArrayList[n + 1];
        parents = new int[n + 1];
        visited = new boolean[n + 1];

        // ArrayList의 배열을 만들어 주기 위해 초기화
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        
        // 값 입력받기
        for (int i = 1; i < n ; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 각각에 추가를 해주는 이유 : 연결된 것이기 때문
            list[x].add(y);
            list[y].add(x);
        }

        for (int i = 1; i <= n; i++) {
            if(!visited[i]) { // dfs탐색을 하면서 탐색이 되지 않은 곳이라면
                dfs(i);
            }
        }
        
        // 2번 노드부터 출력을 하니까
        for (int i = 2; i <= n; i++) {
            System.out.println(parents[i]);
        }
    }

    private static void dfs(int x){
        if(visited[x]) { // 탐색했던 곳이면 탐색 필요가 없으니까 return
            return;
        }
        
        visited[x] = true; // 탐색을 했다고 표시
        
        for (int i : list[x]) {
            if(!visited[i]) { // 탐색하지 않았다면
                parents[i] = x; // 부모 노드를 입력
                dfs(i); // dfs 탐색
            }
        }
    }
}