[백준] 11725번: 트리의 부모 찾기

📖 문제 설명

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

💦 입력

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

🍩 출력

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

🤯 풀이 로직

1. 간선 연결
2. dfs로 부모 테이블 체우기
3. 부모 테이블 출력

1번이 루트 이므로 dfs를 1번 정점부터 시작한다. 1번과 연결된 정점중에서 방문한 적이 없으면 dfs를 재귀호출한다. 이때, dfs로 재귀호출하기 전에 부모 테이블을 갱신해준다.
1번이 루트라고 정해져있기때문에 1번부터 dfs를 타고 내려가면 dfs 함수로 먼저 들어온 정점일수록 루트쪽에 가깝에 위치한다는 것을 알 수 있다. 이를 이용하여 현재 dfs에 매개변수로 들어온 정점은 부모가 되고 이 부모에 연결되어 다음 dfs의 매개변수로 전달될 정점이 자식이 된다.

필요한 자료형

• 노드 개수 : int n
• 그래프 : ArrayList<Integer>[] graph = new ArrayList[n+1] => 각 graph[i]는 new ArrayList<>()로 객체 생성
• 방문 확인 : boolean[] visited = new boolean[n+1]
• 부모 테이블 : int[] parent = new int[n+1]

필요한 함수

1. 간선 연결 함수

• 두 정점 입력
  • 각 정점에 서로의 간선 추가 (양방향 연결)

2. dfs

• 매개변수로 받은 정점 방문 체크
  • 이 정점과 연결된 정점 탐색
    • 방문한 적이 없으면
      • 현재 dfs에 진입한 매개변수가 부모, 다음 dfs를 호출하기 위해 전달된 매개변수가 자식
      • dfs 재귀호출

3. 부모 테이블 출력 함수

• 노드 2번부터 n번까지 부모 테이블 배열 출력

💭 회고

트리를 구현할 때 dfs를 이용할 수 있다는 점이 새롭게 느껴졌다.

🌠 배운것

• dfs를 이용하여 트리를 구현하는 방법을 배웠다.
• ArrayList[]를 이용하여 2차원 배열을 만드는 방법을 배웠다.
• ArrayList[]로 2차원 배열을 만들면 가장 바깥쪽에 ArrayList 객체를 생성해주고, 안쪽에도 각각 ArrayList 객체를 생성해주어야 함을 배웠다.

🔑 코드

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

public class Main {
    static int n; // 노드 개수
    static ArrayList<Integer>[] graph; // 그래프
    static boolean[] visited; // 방문 확인
    static int[] parent; // 부모 테이블

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = br.readLine().split(" ");
        n = Integer.parseInt(tokens[0]);
        graph = new ArrayList[n+1];
        visited = new boolean[n+1];
        parent = new int[n+1];
        for (int i=0; i<n+1;i++) {
            graph[i] = new ArrayList<>();
        }

        // 그래프 연결
        for (int i=0; i<n-1; i++) {
            tokens = br.readLine().split(" ");
            int a = Integer.parseInt(tokens[0]);
            int b = Integer.parseInt(tokens[1]);

            graph[a].add(b);
            graph[b].add(a);
        }
    }

    static void dfs(int vertex) {
        visited[vertex] = true;

        for (int nxt: graph[vertex]) {

            if (!visited[nxt]) {
                parent[nxt] = vertex;
                dfs(nxt);
            }
        }
    }

    static void output() {
        for (int i=2; i<=n; i++) {
            System.out.println(parent[i]);
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        dfs(1);
        output();
    }

}