[백준] 11725. 트리의 부모 찾기 / Java

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

11725번: 트리의 부모 찾기

---

문제 풀이 

루트 노드인 1부터 DFS 탐색을 하기 때문에 DFS가 시작되는 노드가 부모가 되고, 이 노드에 연결되어 있으면서 아직 탐색되지 않은 노드를 찾는다면 그 노드가 자식 노드가 되게 된다.

 

다시 말해, 루트 노드로부터 아직 탐색되지 않은 노드를 탐색하며 해당 노드가 어느 노드로부터 왔는지를 찾아 parent[]에 저장한다.

소스 코드

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

public class BOJ11725 {
    static int N;  // 노드 개수
    static int[] parent;  // 각 노드의 부모 노드
    static boolean[] visited;
    static List<Integer>[] graph;  // 트리 정보를 담은 리스트 배열
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

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

        dfs(1);

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

    static void dfs(int index) {
        visited[index] = true;
        for (int i : graph[index]) {
            if (!visited[i]) {
            	// index 노드에 연결된 노드 중 아직 탐색되지 않은 노드 i는 index 노드를 부모로 갖는다
                parent[i] = index;  
                dfs(i);
            }
        }
    }

}