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

인접한 노드 리스트

static List<ArrayList<Integer>> list; // 인접한 노드들을 나타내기위해 이차원배열

인덱싱

배열의 인덱스와 노드번호를 일치 시키려면 인덱싱 처리 필요
 isVisited = new boolean[N+1]; // 인덱스와 노드번호 일치하려고 N+1
 parents = new int[N+1];

2차원배열 초기화

list = new ArrayList<>();
 for (int i = 0; i <= N; i++) { // N+1
	list.add(new ArrayList<>());
 }

dfs

private static void dfs(int v) {
        isVisited[v] = true;

        for(int node : list.get(v)) { // v번 노드의 인접리스트 중에
            if(!isVisited[node]) { // 노드를 방문한적 없으면 그 노드의 부모는 v
                parents[node] = v;
                dfs(node);
            }
        }
    }

전체풀이

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

public class Main {
    static int N;
    static int[] parents;
    static boolean[] visited;
    static List<ArrayList<Integer>> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        parents = new int [N + 1];
        visited = new boolean [N + 1];
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }

        for(int i = 0; i < N - 1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            list.get(v1).add(v2);
            list.get(v2).add(v1);
        }

        dfs(1);

        for(int i = 2; i < N + 1; i++){
            System.out.println(parents[i]);
        }
    }
    static void dfs(int v){
        visited[v] = true;

        for (int i : list.get(v)) {
            if(!visited[i]){
                parents[i] = v;
                dfs(i);
            }
        }
    }
}

풀이

• 문제에서 루트가 1이라고 했으니까 먼저 visit 처리하고 탐색하면 부모인지 아닌지 판별가능
• 즉 지금 탐색하고 있는 노드의 인접한 리스트를 확인했을때(list.get(v)) 방문하지 않은 노드가 있다면 그 방문하지 않은 노드의 부모는 현재 탐색하고 중인 노드(v)가 됨!