백준 11725번 트리의 부모 찾기 S1 - 트리

 

입력들이 주루루 주어지고 1이 루트로 기준이 된다.

 

입력예제 처럼 주어지게 되면. 그림과 같이 입력이 들어온다.

 

1이 root 가 된다면 이처럼 표기할 수 있겠다.

따라서 각 자리의 부모를 나타내면

2 : 4

3 : 6

4 : 1

5 : 3

6 : 1

7 : 4 이다.

 

Level 별로 나타내는게 문제의 핵심이기때문에 Map에 레벨과 리스트를 넣어 tree를 구성해주었다.

static Map<Integer, List<Integer>> tree = new HashMap<>();

 

이후 선언된 tree에 입력을 처리할때 computeIfAbsent를 활용해서 기존 값이 있다면 추가, 없었다면 새로 리스트를 넣어주었다. 

tree.computeIfAbsent(a, k -> new ArrayList<>()).add(b);

 

dfs 재귀를 통해서 모든 트리를 찾아 주었는데, parents 배열에 현재값의 부모를 넣어주었다.

현재 노드에 자식이 없는경우를 방지하기 위해서 getOrDefault를 통해 null 을 방지해주었다

 public static void dfs(int current, int parent) {
        parents[current] = parent;
        for (int child : tree.getOrDefault(current, new ArrayList<>())) {
            if (child != parent) {
                dfs(child, current);
            }
        }
    }

 

import java.io.*;
import java.util.*;
 
public class Main { //  Boj_11725_트리의 부모 찾기
    static int N;
    static Map<Integer, List<Integer>> tree = new HashMap<>();
    static int[] parents;
 
    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];
 
        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            tree.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
            tree.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
        }
 
        dfs(1, 0);
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= N; i++) {
            sb.append(parents[i]).append("\n");
        }
        System.out.println(sb);
    }
    public static void dfs(int current, int parent) {
        parents[current] = parent;
        for (int child : tree.getOrDefault(current, new ArrayList<>())) {
            if (child != parent) {
                dfs(child, current);
            }
        }
    }
}