백준 13549번 : 숨바꼭질3 (다익스트라)
이번 문제는 1697번 숨바꼭질 문제의 연장선이다.
간선 가중치가 전부 동일하게 1이었던 1697번 문제와는 달리 이번 문제는 0과 1로 나뉜다.
이 때문에 노드 사이 간선의 가중치가 같을 때는 BFS를 사용하는 것이 최단 거리를 구하고자하는 목적에 더 알맞지만, 이번 문제는 다익스트라 알고리즘을 활용해서도 풀 수 있다.
(사실 간선의 가중치가 0과 1 밖에 없고, 최단 거리를 찾는 문제이기 때문에 BFS가 더 효율적이다.)
기존 1697번 문제에서 살짝 수정을 가하면 쉽게 풀어낼 수 있다.
기존 코드는 맨 처음 제시한 링크를 들어가서 확인하면 된다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
static boolean[] visited;
static int max = 100001;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
arr = new int[max];
visited = new boolean[max];
bfs(n, k);
System.out.println(arr[k]);
}
public static void bfs(int start, int end) {
visited[start] = true;
arr[start] = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(start);
while (!q.isEmpty()) {
int cur = q.poll();
if (cur == end) {
break;
}
if (cur * 2 < max && !visited[cur * 2]) {
q.offer(cur * 2);
visited[cur * 2] = true;
arr[cur * 2] = arr[cur];
}
if (cur - 1 >= 0 && !visited[cur - 1]) {
q.offer(cur - 1);
visited[cur - 1] = true;
arr[cur - 1] = arr[cur] + 1;
}
if (cur + 1 < max && !visited[cur + 1]) {
q.offer(cur + 1);
visited[cur + 1] = true;
arr[cur + 1] = arr[cur] + 1;
}
}
}
}
BFS 알고리즘을 문제에 맞게 수정했는데, 우선 *2 만큼 이동하는 순간이동에 한해 변경 사항이 있다.
순간 이동 시에는 간선의 가중치가 0이기 때문에 순간 이동했을 경우 거리를 추가해주지 않아도 된다.
그렇기 떄문에 arr[cur]에 추가했던 1은 삭제했다.
또한, 가중치가 0인 순간 이동이 우선 시 되어야 하므로 세 개의 조건문 중 가장 앞으로 옮겼다.
이렇게만 작성해서 제출해도 효율적으로 탐색이 가능하다.
다만, 다익스트라 알고리즘을 탐구하기 위해 작성하는 만큼 해당 알고리즘을 이어서 작성할 것이다.
기본적인 다익스트라 알고리즘의 개념에 대해서는 아래의 블로그들을 참고했다.
알고리즘에 대해 순차적으로 보기 위해 우선 Main 클래스에 선언, 초기화된 멤버 변수에 대해 살펴볼 것이다.
1
2
3
4
public class Main {
public static final int INF = (int)1e9;
public static int n, k;
public static int[] arr = new int[100001];
n과 k는 입력에 대한 변수이기 때문에 넘어가고
arr은 문제에서 제시된 최대 크기 만큼 초기화했다.
INF는 무한대를 의미한다.
이 값은 시작점에서 각 노드까지의 최단 거리를 저장하는 배열 arr을 초기화하는 데 사용된다.
처음에는 모든 위치까지의 거리가 무한대라고 가정하고 시작하고, 알고리즘을 진행하면서 더 짧은 거리를 발견하게 되면 이 값을 업데이트한다.
메인 함수는
1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
Arrays.fill(arr, INF);
dijkstra(n);
System.out.println(arr[k]);
}
다익스트라 알고리즘을 실행하기 전에 각 위치까지의 최단 거리를 저장하기 위한 배열인 arr의 초기 값을 INF로 설정한다.
이제 다익스트라 알고리즘이다.
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
// 다익스트라
public static void dijkstra(int start) {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
arr[start] = 0;
while(!pq.isEmpty()) {
int[] node = pq.poll();
int now = node[0];
int dist = node[1];
if (arr[now] < dist) continue;
if (now - 1 >= 0) {
int cost = arr[now] + 1;
if (cost < arr[now - 1]) {
arr[now - 1] = cost;
pq.offer(new int[]{now - 1, cost});
}
}
if (now + 1 < 100001) {
int cost = arr[now] + 1;
if (cost < arr[now + 1]) {
arr[now + 1] = cost;
pq.offer(new int[]{now + 1, cost});
}
}
if (now * 2 < 100001) {
int cost = arr[now];
if (cost < arr[now * 2]) {
arr[now * 2] = cost;
pq.offer(new int[]{now * 2, cost});
}
}
}
}
다익스트라 알고리즘의 흐름은 다음과 같다.
- 우선 순위 큐를 생성한다.
- 이 큐에는 각 위치와 그 위치까지의 최단 거리 정보를 담은 배열이 저장된다.
- 큐의 우선 순위는 배열의 두 번째 요소(거리 정보)에 따라 결정된다.
- 시작점과 그 거리인 0을 담은 배열을 큐에 추가하고 arr 배열의 시작점 위치 값을 0으로 설정한다.
- 이후 큐가 빌 때까지 아래 과정을 반복한다.
- 큐에서 가장 거리가 짧은 위치 정보를 poll한다.
- 만약 이 위치까지의 최단 거리가 이미 알려진 거리인 arr[now]보다 길다면, 이 위치는 탐색할 필요가 없으므로 continue 한다.
- 이 위치에서 -1, +1, *2로 이동할 수 있는 새로운 위치를 탐색한다.
- 각 이동은 다음과 같이 처리된다.
- 이동한 위치까지의 새로운 거리인 cost를 계산한다. -1과 +1로 이동하는 경우는 현재 거리에 1을 더하고 *2로 이동하는 경우는 현재 거리를 그대로 사용한다.
- 만약 이 거리가 이 위치까지의 기존 최단 거리보다 짧다면, 이 위치까지의 최단 거리를 새로운 거리로 업데이트하고, 이 위치와 새로운 거리 정보를 큐에 추가한다.
- 반복 후 큐가 빈다면, arr 배열에는 시작점에서 각 위치까지의 최단 거리가 저장된다.
- 마지막으로 메인 함수에서 arr[k]를 출력해 최단 거리를 출력한다.
이렇게 다익스트라 알고리즘은 각 위치를 방문하면서 그 위치까지의 최단 거리를 업데이트하고, 이를 바탕으로 다음에 방문할 위치를 결정하여 최단 거리를 찾아낸다.
생김새는 BFS와 비슷하지만 논리적인 흐름이 다르다.
전체 소스코드는 다음과 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static final int INF = (int)1e9;
public static int n, k;
public static int[] arr = new int[100001];
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
Arrays.fill(arr, INF);
dijkstra(n);
System.out.println(arr[k]);
}
// 다익스트라
public static void dijkstra(int start) {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
arr[start] = 0;
while(!pq.isEmpty()) {
int[] node = pq.poll();
int now = node[0];
int dist = node[1];
if (arr[now] < dist) continue;
if (now - 1 >= 0) {
int cost = arr[now] + 1;
if (cost < arr[now - 1]) {
arr[now - 1] = cost;
pq.offer(new int[]{now - 1, cost});
}
}
if (now + 1 < 100001) {
int cost = arr[now] + 1;
if (cost < arr[now + 1]) {
arr[now + 1] = cost;
pq.offer(new int[]{now + 1, cost});
}
}
if (now * 2 < 100001) {
int cost = arr[now];
if (cost < arr[now * 2]) {
arr[now * 2] = cost;
pq.offer(new int[]{now * 2, cost});
}
}
}
}
}
BFS 탐색 결과는 아래와 같다. 
다익스트라 알고리즘에 대해 이해하는 시간이 길었다.
완벽하진 않지만 활용하려고 노력을 해볼 수 있을 것이다.
다만, 가중치가 다양해진다면 머리가 아프겠지만…