일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- 프로그래머스
- 그래프 이론
- 완전탐색
- DP
- 자바
- 알고리즘
- 개발자취업
- 99클럽
- DFS
- 스프링 핵심 원리 - 기본편
- 그래프
- 코딩테스트준비
- 우선순위큐
- 항해99
- 네트워크 계층
- 동적 프로그래밍
- 정렬
- Til
- 그리디
- Java
- 브루트포스
- 데이터베이스
- 트리
- 백준
- BinarySearch
- Spring
- 백트래킹
- BFS
- lower bound
- 스프링
- Today
- Total
AtraFelis's Develop Diary
[백준] 11725 - 트리의 부모 찾기 (JAVA) 본문
SILVER II
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
풀이
난이도 보고 쉽게 풀 수 있겠거니 했다가, 통수에 통수를 맞은 문제였다.
일단 문제의 풀이 방향은 이렇다.
- 주어지는 입력값을 그래프로 만든다.
- 1번 노드부터(1번은 무조건 root이므로) 차례대로 그래프를 탐색한다.
BFS
든DFS
든 상관없으나 나는BFS
를 사용하였다. - 1번 노드와 연결된 노드는 무조건 1번 노드를 부모로 갖는다.
- 이미 부모를 찾은 노드와 연결된 노드들은 그 노드를 부모로 갖는다. (트리이므로.)
이렇게 모든 노드를 순회하여 탐색하면 모든 노드들의 부모 노드를 찾을 수 있다.
나는 이 과정에서 두 가지 문제에 직면했다.
인접 행렬 그래프
보통 문제 풀이를 할 때, 나는 인접 행렬 방식을 이용해 그래프를 표현한다. 이 방법이 익숙해졌기 때문이고 쉽기 때문이다. (정확히는 쉽다고 생각하고 있었다.)
하지만 이 방식은 무조건 주어지는 노드의 수(n
)만큼의 크기를 갖는 배열을 할당해주어야 한다는 문제가 있다. 즉, 시작하자마자 무조건 n*n
크기의 메모리를 소모하게 된다.
그래서 인접 리스트 방식을 이용해 그래프를 표현해주었다.
인접 리스트 방식이 왜 더 메모리를 적게 소모하는가?
만약 1000개의 노드가 주어졌다고 가정했을 때, 인접 행렬이라면 무조건 1000*1000
을 할당해주어야 한다. 하지만 인접 리스트라고 한다면, 1000*(각 노드와 연결된 edge 수)
만큼의 크기만 잡아먹게 된다.
그러므로 생으로 Array
를 쓰는 것이 아니라 List
를 이용하면 쉽게 구현할 수 있다.
이렇게 일단 메모리 초과는 해결했다.
LinkedList vs ArrayList
LinkedList< LinkedList<Integer> > graph = new LinkedList<>();
for (int i = 0; i < n+1; i++) {
graph.add(new LinkedList<>());
}
그래프를 할당할 List
를 선언하는 부분이다. 여기서 무엇이 문제일까?
LinkedList
와 ArrayList
에서 특정한 원소를 찾아가는 방식을 생각해보면 쉽게 답을 알 수 있다.
LinkedList
는 특정한 원소를 찾아가려면, 무조건 이전 index
를 거쳐야만 한다. 그렇기에 BFS
등을 하는 과정에 있어서 시간을 엄청나게 잡아먹을 수밖에 없는 것이다.
만약, graph.get(10000)
을 하려고 한다면, 0번 원소부터 10000번까지 차례대로 거쳐가야 한다. 하지만 ArrayList
는 한 번에 그 값으로 찾아간다. 이 부분에서 시간이 차이가 나게되는 것이었다.
따라서 위의 LinkedList를,
ArrayList< LinkedList<Integer> > graph = new ArrayList<>();
for (int i = 0; i < n+1; i++) {
graph.add(new LinkedList<>());
}
이렇게 바꾸면 된다.
(그냥 맨 처음부터 ArrayList
로 사용했으면 이런 문제도 없었을 텐데. 뭐, 그래도 삽질 해보면서 크게 배웠으니 좋다고 생각해야지 뭐.)
전체 코드
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int n = Integer.parseInt(br.readLine());
ArrayList< LinkedList<Integer> > graph = new ArrayList<>();
for (int i = 0; i < n+1; i++) {
graph.add(new LinkedList<>());
}
int[] parent = new int[n+1];
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n-1; i++) {
stk = new StringTokenizer(br.readLine());
int node1 = Integer.parseInt(stk.nextToken());
int node2 = Integer.parseInt(stk.nextToken());
graph.get(node1).add(node2);
graph.get(node2).add(node1);
}
queue.add(1);
parent[1] = 1;
while(!queue.isEmpty()) {
int node = queue.remove();
for (int value : graph.get(node)) {
if (parent[value] == 0) {
parent[value] = node;
queue.add(value);
}
}
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 2; i <= n; i++)
bw.write(parent[i] + "\n");
bw.flush();
bw.close();
}
}
'Algorithm > 백준' 카테고리의 다른 글
[백준] 1005 - ACM Craft (JAVA) (0) | 2024.06.24 |
---|---|
[백준] 12865 - 평범한 배낭 (JAVA) (0) | 2024.05.21 |
[백준] 16953 - A → B (JAVA) (0) | 2024.05.14 |
[백준] 20529 - 가장 가까운 세 사람의 심리적 거리 (C언어) (0) | 2024.04.16 |
[백준] 5525 - IOIOI (C언어) (0) | 2024.04.14 |