[JAVA] # 11725 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

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

public class Main {

    static int N;
    static List<Integer>[] graph;
    static boolean[] visited;
    static int[] parents;

    public static void init_graph() {
        for(int i = 0; i < N + 1; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        while(!queue.isEmpty()) {
            int e = queue.poll();
            for (int adjNode : graph[e]) {
                if(!visited[adjNode]) {
                    parents[adjNode] = e;
                    queue.add(adjNode);
                    visited[adjNode] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;
        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N + 1];
        parents = new int[N + 1];
        visited = new boolean[N + 1];
        init_graph(); // 인접그래프 초기화
        for(int i = 0; i < N - 1; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        
        bfs(1);
        
        for(int i = 2; i <= N; i++) {
            bw.write(parents[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

풀면서 속이 답답-했다

 

문제를 어떻게 풀어야 하는지도 어려웠던 것도 있는데

 

제일 큰 문제는 왜인지 모르는 시간초과 문제 때문이었다.

이런 경우가 제일 답답한 것 같다.

 

다른사람 코드를 찾아보니까 나랑 알고리즘 방식은 똑같은데 내 코드는 시작하자마자 시간초과가 뜨는것이다

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static LinkedList<LinkedList<Integer>> graph = new LinkedList<>();
    static boolean[] visited;
    static int[] parents;

    public static void init_graph() {
        for(int i = 0; i < N + 1; i++) {
            graph.add(new LinkedList<>());
        }
    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        while(!queue.isEmpty()) {
            int e = queue.poll();
            for (Integer adjNode : graph.get(e)) {
                if(!visited[adjNode]) {
                    parents[adjNode] = e;
                    queue.add(adjNode);
                    visited[adjNode] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;
        N = Integer.parseInt(br.readLine());
        parents = new int[N + 1];
        visited = new boolean[N + 1];
        init_graph(); // 인접그래프 초기화
        for(int i = 0; i < N - 1; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            graph.get(a).add(b); // 양방향 인접그래프 생성
            graph.get(b).add(a); // 양방향 인접그래프 생성
        }
        bfs(1);
        for(int i = 2; i <= N; i++) {
            bw.write(parents[i]);
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

시간초과가 나는 코드.

 

정답이 된 코드랑 무슨 차이가 있었던 것일까?

 

유일한 차이점은 인접리스트 그래프를 구현하는 방식의 차이.

(인접행렬은 10만x10만 사이즈라 메모리 초과로 사용할 수 없다)

 

하나는 LinkedList 속에 LinkedList를 이용하여 풀이한 방식이고,

다른 하나는 List 배열(?)을 사용하여 풀이한 방식

 

내부 로직은 똑같고 그냥 그래프를 구현하는 방식만 차이가 있었는데 

아무래도 연결리스트에 연결리스트 담아놓는게 속도면에서 조금 떨어지는 것 같다.

 

앞으로는 연결그래프 구현할때 List배열을 사용하는 걸로 해야겠다..

 

---

 

문제 풀이는 그냥 연결그래프를 이은 다음에 1번 노드부터 탐색하면서 부모노드를 찍어가면 되는 문제였다.

 

 

쩝.. 해결!