백준 2644번 : 촌수계산 (인접 행렬과 인접 리스트)
이 문제는 전체 사람 수 n이 주어지고, 그 다음으로는 촌수를 계산해야하는 서로 다른 사람의 번호, 그 다음은 부모 자식간의 관계의 개수인 m, m 이후로 해당 관계를 나타내는 두 번호 x,y가 입력된다.
즉, x,y의 관계를 보고 촌수를 계산하면 되는 문제이다.
이 문제는 인접 리스트로 풀었는데, 인접 리스트는 이전 문제인 11725번 트리의 부모 찾기 문제를 참고했다.
이외의 정확한 인접 리스트, 인접 행렬의 설명과 장단 점은 아래 두 개의 블로그에 잘 정리되어 있다.
Song’s DLog
주니어 개발자의 대나무숲
각 그래프의 주요 장단 점을 정리하면 아래와 같다.
인접 행렬 :
- 장점:
- 두 노드 간의 연결 여부를 확인하는 것이 O(1)의 시간 복잡도로 빠름.
- 구현이 비교적 간단하고 직관적.
- 단점:
- 모든 노드 쌍에 대해 연결 정보를 저장하므로 메모리 사용량이 크고, 노드의 수가 많은 경우에는 비효율적.
- 희소 그래프(Sparse Graph, 노드 사이의 엣지 수가 노드 수에 비해 상대적으로 적은 그래프)에서는 메모리 낭비가 심각.
인접 리스트:
- 장점:
- 메모리 사용량이 엣지의 수에 비례하므로, 희소 그래프를 표현하는 데 효율적.
- 특정 노드에 연결된 모든 노드를 순회하는 것이 빠르고, BFS나 DFS와 같은 그래프 탐색 알고리즘에 적합.
- 단점:
- 두 노드 간의 연결 여부를 확인하는 데는 O(N)의 시간 복잡도가 필요.
- 인접 행렬에 비해 구현이 조금 더 복잡.
이 문제를 인접 리스트로 푼 이유는 노드 사이의 엣지 수가 노드 수에 비해 상대적으로 적은 그래프이기 때문이다.
다시 말해, 총 노드 수인 n보다 연결된 엣지 수인 m이 더 적기 때문이다.
문제에서는 연결되어 있지 않을 수 있다고 했기 때문에 파악이 가능하다.
반대로 모든 노드가 서로 연결되어 있다면 밀집 그래프로, 인접 행렬이 더 어울렸을 것이다.
인접 행렬과 인접 리스트의 차이를 이번에 알아내어서 이전에 풀었던 문제들도 인접 행렬보다 인접 리스트가 어울렸던게 있었을 수도 있다.
그러나 풀이 당시 이상한 점을 느끼지 못했기 때문에 인접 행렬이 더 맞는 풀이였을 것이다.
문제를 읽고 일차원 배열로 될 것 같은 것들은 대부분 인접 리스트로 풀 수 있었고,
반대로 이차원 배열로 풀어야할 것 같은 것들은 인접 행렬로 풀었었다.
다시 문제로 돌아와
이번 문제는 인접 리스트가 효율적이라 판단 했으며 구현은 11725번 트리의 부모 찾기를 참고하여 진행했다.
해당 문제에서와 같이 인접 리스트의 구현은 다음과 같다.
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
public class Main {
static int n, m, start, end;
static int[] arr;
static boolean[] visited;
static int[] dist;
static ArrayList<Integer>[] tree;
public static void main(String[] args) throws java.io.IOException {
...
tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
tree[x].add(y);
tree[y].add(x);
}
}
}
중간은 생략하고 인접 리스트 구현 방식만 살펴보면
정수 래퍼 타입을 참조하는 ArrayList 타입의 배열을 생성하여 tree라고 명명하였고, 해당 트리의 크기를 최대명수 n 만큼 초기화했다.
또한 tree 배열 내부의 값들도 일일히 초기화했다.
이를 통해 배열의 인덱스는 부모 노드, 해당 인덱스 내부의 리스트는 연결된 자식 노드들로 표현된다.
해당 부분만 출력하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
테스트 케이스 :
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
tree 형태 :
[[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]
9개의 노드들이 어디와 연결되어 있고 상하관계를 표현할 수 있다.
이 때 주의할 점은 노드는 1번 부터 시작이기 때문에 0번 인덱스의 값은 무시한다.
이것 때문에 배열을 하나씩 크게 잡은 것이다.
이 인접 리스트를 보기 쉽게 표현하면 아래와 같다.
1
2
3
4
5
6
7
8
9
1 → [2, 3]
2 → [1, 7, 8, 9]
3 → [1]
4 → [5, 6]
5 → [4]
6 → [4]
7 → [2]
8 → [2]
9 → [2]
다음으로 탐색을 진행해야하는데, 이 문제의 경우 start에서 end까지 도달하는 횟수를 리턴해야하기 때문에 이동할 때마다 횟수를 저장해줄 무언가가 필요하다.
처음에는 count 변수를 만들어 진행했는데, 각 노드들로 진입을 하기만해도 횟수가 올라 dist라는 배열을 사용하는 것으로 변경했다.
이 dist 배열은 크기를 노드의 수 만큼 초기화하고 각 인덱스가 노드의 번호를 나타낸다.
1
dist = new int[n + 1];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void bfs(int start) {
visited[start] = true;
Queue<Integer> q = new LinkedList<>();
q.offer(start);
while (!q.isEmpty()) {
int cur = q.poll();
if (cur == end) {
return;
}
for (int child : tree[cur]) {
if (!visited[child]) {
q.offer(child);
visited[child] = true;
dist[child] = dist[cur] + 1;
}
}
}
}
bfs 탐색의 진행 방식은 기존과 동일하되, 시작된 노드는 제외하고 현재 노드에서 다음 노드로 옮겨 갈때마다 해당 노드에 1씩 가중치를 더 한다.
또한, while 문 내부에 조건문을 보면 알겠지만 현재 노드가 end와 동일해지면 종료지점에 도달한 것으로 파악하여 탐색을 종료한다.
이 로직으로 시작 노드 부터 연결된 노드로 이동할 때마다 1씩 횟수가 더 해지고, 종료 노드에 도달하면 해당 노드에 도달하는 데 걸린 총 횟수가 저장된다.
만약 도달하지 못한다면 연결이 되어 있지 않다는 의미이고 종료 노드의 값이 0으로 끝난다.
1
2
3
4
5
if (dist[end] == 0) {
System.out.println(-1);
} else {
System.out.println(dist[end]);
}
이로써 인접 리스트를 활용한 시작 노드부터 종료 노드까지의 횟수를 구할 수 있고, 이는 곧 문제에서 원하는 촌수가 된다.
전체 소스 코드는 다음과 같다.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, start,end;
static int[] arr;
static boolean[] visited;
static int[] dist;
static ArrayList<Integer>[] tree;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
m = Integer.parseInt(br.readLine());
arr = new int[n + 1];
visited = new boolean[n + 1];
dist = new int[n + 1];
tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
tree[x].add(y);
tree[y].add(x);
}
bfs(start);
if (dist[end] == 0) {
System.out.println(-1);
} else {
System.out.println(dist[end]);
}
}
static void bfs(int start) {
visited[start] = true;
Queue<Integer> q = new LinkedList<>();
q.offer(start);
while (!q.isEmpty()) {
int cur = q.poll();
if (cur == end) {
return;
}
for (int child : tree[cur]) {
if (!visited[child]) {
q.offer(child);
visited[child] = true;
dist[child] = dist[cur] + 1;
}
}
}
}
}
참고로 이 문제는 DFS로도 풀 수 있을 거 같긴한데, 전체 탐색보다는 최단 거리 탐색이 어울린다.
이번 기회에 인접 행렬과 인접 리스트의 장단점, 어디에 사용해야할지에 대해 알고 간다.
문제들이 거의 인접 행렬로 푸는 문제들이었어서 오히려 인접 리스트가 나오면 헷갈린다.
제목에도 써놓았으니 인접 리스트, 혹은 행렬 둘 중 어느것으로 풀어야할지나 장단점에 대해 알고 싶다면 이 포스트로 돌아오면 된다.