[백준 JAVA] 11725번: 트리의 부모 찾기

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

 

 

 

방향을 알 수 있는 정보가 루트가 1이라는거 밬에 없기 때문에 처음에 어떻게 트리를 구현해야할지 막막했다.

 

우선 트리의 값들을 양방향 그래프라고 생각하고 전부 받아 온 뒤 1부터 연결되어 있는 노드를 들여다 보며 차수를 계산한 뒤 배열에 저장해두고 나중에 그래프에서 꺼낸 뒤 연결된 노드간의 차수가 가장 작은걸 출력하는 방식으로 풀어보았다.

 

N < 100,000 이고 시간복잡도는 O(N)이 되므로 풀이가 가능할꺼같다.

 

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

public class Main {
    public static int N;
    public static int[] degree;
    public static List<Integer>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        // 1. 입력받기
        N = Integer.parseInt(br.readLine());
        degree = new int[N + 1];
        list = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++){
            list[i] = new ArrayList<>();
        }
        // 1-1. 양방향 그래프 입력
        for(int i = 0; i < N - 1; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
        // 2. 차수 계산
        Queue<Integer> q = new LinkedList<>();
        int cnt = 2;
        q.offer(1);
        degree[1] = 1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                int cur = q.poll();
                for(int child : list[cur]) {
                    if(degree[child] == 0) {
                        degree[child] = cnt;
                        q.offer(child);
                    }
                }
            }
            cnt++;
        }

        // 3. 부모노드 탐색
        for(int i = 2; i <= N; i++){
            int min = Integer.MAX_VALUE;
            int parent = 0;
            for(int j = 0; j < list[i].size(); j++){
                int x = list[i].get(j);
                if(degree[x] < min){
                    min = degree[x];
                    parent = x;
                }
            }
            sb.append(parent).append("\n");
        }

        System.out.println(sb);
    }
}

 

조금 더 깔끔하게 풀 수 있을꺼같은데 어렵다.

 

GPT 피드백 중 참고할 만한 사항들

 

 

1. 용어 혼동: 변수명이 degree인데 실제로는 “차수(인접 노드 수)”가 아니라 “깊이(depth)”입니다. 주석도 “차수 계산”이 아니라 “깊이 계산”이 맞아요. 나중에 본인이 봐도 헷갈릴 수 있으니 depth로 바꾸는 게 좋아요.

 

이건 정말 나중에 면접을 볼때나 의사소통 할때 큰일 날뻔했다. 차수가 아니라 깊이

 

 

2. 2단계 로직 단순화 가능: 지금은 (1) BFS로 깊이 계산 → (2) 모든 노드의 이웃을 돌며 가장 얕은 쪽을 부모로 선택, 이렇게 두 번 돕니다. BFS 중에 바로 parent[child] = cur; 로 기록하면 2단계를 없앨 수 있어요. 시간·코드 모두 더 깔끔해집니다.

 

먼저 깊이를 다 구하고 비교하려고 했는데 생각해보니 BFS중에 충분히 기록할 수 있을꺼같다.

 

3. 큐 구현: LinkedList보다 ArrayDeque가 큐 용도로는 더 빠르고 메모리 효율적입니다.

 

습관적으로 큐를 구현할때 LinkedList를 사용했는데 이건 좀 생각해 볼 여지가 있다.

 

 

4. 방문 체크: 현재는 degree[child] == 0을 방문 체크로 쓰고 있는데, parent 배열을 방문 마킹으로 겸용하면 명확해집니다(parent[nxt] == 0이면 미방문).

 

부모를 깊이를 계산하며 바로 채워주므로 한번에 계산할꺼면 이 방법을 쓰는게 확실히 좋아보인다.

 

5. 재귀 DFS 지양: 자바에서 재귀 DFS는 100k 노드에선 스택오버플로우 위험이 있어요. 현재처럼 반복형 BFS가 안전합니다.

 

재귀에서 스택오버플로우 걱정을 크게 해본적이 없었는데 반드시 참고할만한 사항인것같다.

 

다시 푼 풀이

 

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

public class Main {
    public static int N;
    public static int[] parent;
    public static List<Integer>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        // 1. 입력받기
        N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        list = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++){
            list[i] = new ArrayList<>();
        }
        // 1-1. 양방향 그래프 입력
        for(int i = 0; i < N - 1; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
        // 2. 차수 계산
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        parent[1] = 1;
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int child : list[cur]) {
                if(parent[child] == 0) {
                    parent[child] = cur;
                    q.offer(child);
                }
            }
        }

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

        System.out.println(sb);
    }
}

 

 

BFS라는 풀이방법은 같지만 생각의 전환에 따라 훨씬 간단하게 풀 수 있는 문제였다.

 

풀이 방법이 생각났다고 바로 손대지말고 더 편하고 빠르게 풀 수 있는 방법이 있는지 조금 생가해보는 시간을 가지는것도 좋은듯하다.