[백준 11725] 트리의 부모 찾기 (Java) - 트리, DFS

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

 

트리의 부모 찾기 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 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

 

---

풀이

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

public class Main {
    static int N;
    static int[] parent;
    static ArrayList<Integer>[] tree;
    static boolean[] visited;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 노드개수
        tree = new ArrayList[N+1]; // 노드번호 1번부터 시작
        visited = new boolean[N+1]; // 방문배열 초기화

        // 인접리스트 초기화
        for(int i=1; i<N+1; i++){
            tree[i] = new ArrayList<>();
        }

        StringTokenizer st;
        int node1, node2;
        // 인접노드리스트 입력 받아주기
        for(int i=0; i<N-1; i++){
            st = new StringTokenizer(br.readLine());
            node1 = Integer.parseInt(st.nextToken());
            node2 = Integer.parseInt(st.nextToken());

            // 양방향 연결
            tree[node1].add(node2);
            tree[node2].add(node1);
        }

        parent = new int[N+1]; // 부모노드 저장배열
        DFS(0, 1);

        for(int i=2; i<N+1; i++){
            System.out.println(parent[i]);
        }
    }
    private static void DFS(int parentNode, int node){
        parent[node] = parentNode;
        visited[node] = true;

        // 현재노드의 인접리스트 순회
        for(int now : tree[node]){
            if (!visited[now]){
                DFS(node, now);
            }
        }
    }
}

• 트리(인접리스트)를 활용한 문제
• 노드의 개수N개를 입력으로 받고, 노드번호가 1부터 시작하므로 tree, visited, parent 배열 모두 N+1크기로 선언해준다.
• 노드의 연결정보를 인접리스트에 양방향으로 저장해준다.
• 루트노드 1번부터 DFS를 수행해준다.
  • 입력으로 받은 node의 인접리스트를 순회하면서 방문하지 않은 노드가 있다면,
  • now의 부모노드를 node로 저장해준뒤, DFS(now)를 재귀호출한다.