[문제풀이] B11725 트리의 부모 찾기

트리의 부모 찾기

---

  🪅 에지리스트를 인접리스트로 구현할 수 있는가
  🪅 인접리스트를 루트부터 탐색해가며 parent배열을 완성할 수 있는가
  🪅 DFS를 구현할 수 있는가

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

public class Main {
    static List<Integer>[] tree;
    static boolean[] isVisited;
    static int[] parent;
    public static void DFS(int node) {
        isVisited[node] = true;
        for(int adj : tree[node]) {
            if(isVisited[adj]) continue;
            isVisited[adj] = true;
            parent[adj] = node;
            DFS(adj);
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer token;
        tree = new ArrayList[N+1];

        // 각 배열 ArrayList로 초기화
        for(int i = 0; i < N+1; i++) {
            tree[i] = new ArrayList<>();
        }

        // 1 ~ 7
        isVisited = new boolean[N+1];

        // 1 ~ 7
        parent = new int[N+1];

        // 에지리스트 -> 인접리스트, N-1개의 연결정보
        for(int i = 0; i < N-1; i++) {
            token = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(token.nextToken());
            int v = Integer.parseInt(token.nextToken());
            tree[u].add(v);
            tree[v].add(u);
        }
        //test 출력
//        for(int i = 1; i < N+1; i++) {
//            System.out.println(i + ": " + tree[i]);
//        }

        DFS(1);

        for(int i = 2; i < N+1; i++) {
            System.out.println(parent[i]);
        }
    }
}

💡 문제 접근 방법
에지리스트를 인접리스트로 바꾸는 과정에서 부모가 누군지 모름으로
일단 그래프 양방향 이동 가능하게 만들었다.
그 후에, 루트노드를 1로 본다고 했으니, DFS 탐색으로 1부터 시작해서 방문배열을 채워가며
방문한 노드이면 넘기고, 방문하지 않은 배열이면 바로 인접노드의 부모가 현재 노드임을 parent배열에
채워가며 parent배열을 완성할 수 있었다.