[B11725][트리의 부모 찾기][java]

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

 

 

풀이 (DFS)

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 Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<List<Integer>> list = new ArrayList<>();
        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 start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list.get(start).add(end);
            list.get(end).add(start);
        }

        int[] parent = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        
        dfs(list, parent, visited, 1);  // 1번 노드로 시작해서, 

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

    private static void dfs(List<List<Integer>> list, int[] parent, boolean[] visited, int node) {
        visited[node] = true; // 해당 노드를 방문했다고 체크 
        
        if (list.get(node).size() == 1) {
            int v = list.get(node).get(0);
            if(!visited[v]){
                parent[v] = node;
                dfs(list, parent, visited, v);
            }
        }
        
        for (int child : list.get(node)) { // 해당 노드들의 자식 노드들을 반복해서 
            if (!visited[child]) { // 방문하지 않은 노드일 경우
                parent[child] = node; // 해당 노드를 부모 노드로 설정 후
                dfs(list, parent, visited, child); // 자식 노드에 대해 dfs 재귀 호출 
            }
        }
    }
}

 

코드 (BFS)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] list = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list[start].add(end);
            list[end].add(start);
        }

        int[] parent = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : list[node]) {
                if (!visited[next]) {
                    parent[next] = node;
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(parent[i]).append("\n");
        }

        System.out.println(sb);
    }
}