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

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

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

import java.io.*; import java.util.*; public class Main { static int N; static List[] 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 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] + "

"); } 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> 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 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번 노드부터 탐색하면서 부모노드를 찍어가면 되는 문제였다.

쩝.. 해결!

from http://sedangdang.tistory.com/122 by ccl(A) rewrite - 2021-09-15 22:27:00