가장 먼 노드
문제정의
1번 노드로부터 가장 멀리 떨어진 노드가 총 몇 개인지 계산하는 문제이다.
문제풀이
전체 코드는 다음과 같다. 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
65import java.util.*;
public class FarthestNode {
//프로그래머스 level3 가장 먼 노드
public static void main(String[] args) {
int n = 6;
int[][] edge = {
{3, 6},
{4, 3},
{3, 2},
{1, 3},
{1, 2},
{2, 4},
{5, 2}
};
//adjacency list
ArrayList<ArrayList<Integer>> adj_list = new ArrayList<ArrayList<Integer>>(n+1);
for(int i = 0; i <= n; i++)
adj_list.add(new ArrayList<Integer>());
for(int i = 0; i < edge.length; i++)
{
adj_list.get(edge[i][0]).add(edge[i][1]);
adj_list.get(edge[i][1]).add(edge[i][0]);
}
//bfs
int[] distance = new int[n+1];
boolean[] visited = new boolean[n+1];
Queue<Integer> q = new LinkedList<>();
q.add(1);
while(!q.isEmpty())
{
int root = q.poll();
visited[root] = true;
int depth = distance[root]+1;
for(int i : adj_list.get(root))
{
if(!visited[i])
{
distance[i] = depth;
visited[i] = true;
q.add(i);
}
}
}
int max = 0;
for(int i = 1; i < distance.length; i++)
max = Math.max(max, distance[i]);
int answer = 0;
for(int i = 1; i < distance.length; i++)
answer = distance[i] == max ? answer+1 : answer;
System.out.println(answer);
}
}depth(깊이)를 계산하여 제일 큰 값을 가지는 노드가 총 몇 개인지 세어본다. 이번 문제에서는 간선이 많기 때문에 행렬형태로 연결을 포함할 수 없다. 그래서 adjacency list를 통해 구현하였다.
그래프를 모두 표시하고 난 뒤, bfs를 한다. 큐를 선언하고 각 노드의 깊이를 저장할 distance를 선언한다. 1번노드부터 bfs를 시작할 것이므로, 1을 큐에 삽입한다.
이제 큐에서 1을 꺼내 루트로 생각하고 방문여부를 나타내는 visited를 true로 한다. root와 인접한 노드들은 root+1의 깊이를 가지므로 이 값을 depth로 둔다. 이제 인접 리스트를 돌면서 방문하지 않았던 노드들의 깊이를 기록하고 방문기록을 true로 한다.
이 과정을 모두 마치면 distance값 중에 가장 큰 것을 max값으로 한다. 그리고 distance중에 max값이 몇 개가 있는지 세면 정답이다.
adjacency list를 사용하기 때문에, 노드 개수를 V, 간선의 개수를 E라고 한다면 최종 시간복잡도는 \(O(V+E)\)이다.
테스트
필자는 처음에 다익스트라로 풀었는데 구현이 잘못되었는지 계속 틀려서 결국 노트북을 닫았다. 약한 멘탈이 미울 지경이다. 문제점을 못찾겠어서 고민하다가 bfs로도 될 것 같은데라는 생각이 들었다. 하지만 어제는 기력이 다해서 집에서 뻗었다. 결국 다른 사람의 풀이를 찾아보니 다 bfs로 풀었다. 다익스트라로 푼 사람은 못 봤다. bfs로 풀어서 정답을 맞았지만 다익스트라로 풀었을 때 왜 틀렸는지는 아직 의문이다.
