Q. 11725 자바 : 트리의 부모 찾기

Q. 11725 자바 : 트리의 부모 찾기

 

문제 : boj.kr/11725

실버 2 난이도의 문제이다.

 

정점의 개수와 간선이 주어졌을 때(방향성x)

만약 1번 정점이 루트라면 2번 정점부터 부모 노드의 번호를 출력하는 문제이다.

 

처음 이 문제를 봤을 때는 좀 막막했다.

만약 그래프 탐색 문제인줄 모르고 봤다면 문제를 푸는데 시간이 더 오래 걸렸을 것 같다.

고민을 좀 해보니, 간선이 다 주어지므로 모든 간선을 입력받은 뒤에루트가 1이므로 1부터 탐색을 해 가면서 방문 여부를 확인하면 될 것 같다는 생각이 들었다.

 

그래서 아래와 같은 방식으로 풀었다.1. 입력된 모든 간선은 양방향 그래프이므로, 모두 연결한다.2. 1번 정점부터 탐색을 하면서, 어떤 정점에서 호출 됬는지(부모)를 저장한다.

 

시간 복잡도는 정점 N의 최대값이 100,000이므로 아주 클 것 같지만,

모든 정점에 대해 한 번만 탐색 하므로 O(N)으로 해결할 수 있다. 

따라서 시간초과는 걱정하지 않아도 되고, 자료형 역시 int 범위 내에서 모두 해결할 수 있다.

 

풀고 강의자료 코드를 참고하니 좀 더 코드를 줄일 수 있었고,

시간도 유의미하게 차이나서(코드가 읽기도 좀 안좋은 코드였던 것 같다)

이후에 강의자료를 참고해서 다시 풀은 내용도 같이 작성했다.

---

처음 풀었던 풀이는 아래와 같다.

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


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[] parentArr;
    static List<Integer>[] list;

    static boolean[] visit;

    static void input() {

        N = scan.nextInt();
        visit = new boolean[N + 1];
        list = new List[N + 1];
        parentArr = new int[N + 1];

        for (int i = 1; i <= N; i++) list[i] = new ArrayList<>();
        for (int i = 1; i < N; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            list[s].add(e);
            list[e].add(s);
        }
    }

    static void bfs() {

        Queue<Integer> que = new LinkedList<>(); // parent, cur
        visit[1] = true;

        for (int i: list[1]) {
            que.add(1);
            que.add(i);
            visit[i] = true;
        }

        while (!que.isEmpty()) {

            int parent = que.poll();
            int child = que.poll();

            parentArr[child] = parent;
            for (int e: list[child]) {
                if (!visit[e]) {
                    visit[e] = true;
                    que.add(child);
                    que.add(e);
                }
            }
        }
    }

    static void pro() {
        bfs();
        for (int i = 2; i <= N; i++) sb.append(parentArr[i]).append('\n');
        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

---

이후 강의자료를 참고해 다시 작성한 코드는 아래와 같다.

강의 자료를 보며 생각해보니 호출한 부모 정점의 대한 정보는 필요하지만,

이후 자식 정점의 정보는 굳이 bfs에 사용할 필요가 없다는걸 깨달았다.

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


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[] parentArr;
    static List<Integer>[] list;

    static boolean[] visit;

    static void input() {

        N = scan.nextInt();
        visit = new boolean[N + 1];
        list = new List[N + 1];
        parentArr = new int[N + 1];

        for (int i = 1; i <= N; i++) list[i] = new ArrayList<>();
        for (int i = 1; i < N; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            list[s].add(e);
            list[e].add(s);
        }
    }

    static void bfs() {

        Queue<Integer> que = new LinkedList<>(); // parent, cur
        visit[1] = true;
        que.add(1);

        while (!que.isEmpty()) {

            int parent = que.poll();
            for (int child: list[parent]) {
                if (!visit[child]) {
                    visit[child] = true;
                    parentArr[child] = parent;
                    que.add(child);
                }
            }
        }
    }
    
    static void pro() {

        bfs();
        for (int i = 2; i <= N; i++) sb.append(parentArr[i]).append('\n');
        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}