[JAVA42] 11725. 트리의 부모 찾기

11725. 트리의 부모 찾기 (S2)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	91933	41385	29115	42.722 %

 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

---

summary

부모 노드 찾기

• 루트 노드는 1

 

strategy

루트 노드(1)부터 모든 노드 탐색 (BFS, DFS)

• 트리 구조이기 때문에 사이클 없음 (N-1 연결고리 들어옴)

 

note

• 2 ≤ N ≤ 100,000

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

public class Main {

    static int N;
    static int[] parents;
    static ArrayList<Integer>[] tree;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());

        parents = new int[N + 1];
        tree = new ArrayList[N + 1];
        for(int n = 1; n <= N; n++) {
            tree[n] = new ArrayList<Integer>();
        }
        
        for(int n = 1; n < N; n++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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

        parents[1] = 1;

        DFS(1);
        
        for(int i = 2; i <= N; i++) {
            answer.append(parents[i]).append("\n");
        }
        System.out.println(answer.toString());
    }

    public static void DFS(int num) {
        for(int nextNum : tree[num]) {
            if(parents[nextNum] != 0) continue; // 이미 방문한 경우 패스

            parents[nextNum] = num;

            DFS(nextNum);
        }
    }
}

 

문제	결과	메모리	시간	언어코드	길이
11725	맞았습니다!!	69464 KB	684 ms	Java 11 / 수정	1300  B

 

memo

• BFS 로 풀기

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

public class Main {

    static int N;
    static int[] parents;
    static List<Integer>[] tree;
    
    public static void main(String[] args) throws IOException {

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

        N = Integer.parseInt(br.readLine());
        parents = new int[N + 1];
        tree = new ArrayList[N + 1];
        for(int n = 1; n <= N; n++) tree[n] = new ArrayList<>();

        for(int n = 1; n < N; n++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        parents[1] = 1;

        while(!queue.isEmpty()) {
            int current = queue.poll();

            for(int next : tree[current]) {
                if(parents[next] != 0) continue; // 이미 방문한 노드

                parents[next] = current;
                queue.add(next);
            }
        }

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

        System.out.println(answer.toString());
    }
}