문제
해결 방법
- BFS 탐색을 진행하면서 다익스트라 알고리즘을 적용한다.
- 이때 다음 좌표가 흰 방인지, 검은 방인지에 따라 다르게 갱신한다.
정답 코드 - JAVA
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
71
72
73
74
75
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
int[][] visited = new int[n][n];
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < n; j++) {
arr[i][j] = s.charAt(j) - '0';
visited[i][j] = Integer.MAX_VALUE;
}
}
Queue<Pair> q = new LinkedList<>();
if (arr[0][0] == 0) {
visited[0][0] = 1;
q.add(new Pair(0, 0, 1));
} else {
visited[0][0] = 0;
q.add(new Pair(0, 0, 0));
}
while (!q.isEmpty()) {
Pair now = q.poll();
for (int i = 0; i < 4; i++) {
int X = dx[i] + now.x;
int Y = dy[i] + now.y;
if (X < 0 || X > n - 1 || Y < 0 || Y > n - 1) {
continue;
}
// 새롭게 탐색한 거리가 더 크다면 넘어가기
if (arr[X][Y] == 0 && now.k + 1 >= visited[X][Y]) {
continue;
}
// 새롭게 탐색한 거리가 더 크다면 넘어가기
if (arr[X][Y] == 1 && now.k >= visited[X][Y]) {
continue;
}
if (arr[X][Y] == 1) {
q.add(new Pair(X, Y, now.k));
visited[X][Y] = now.k;
} else {
q.add(new Pair(X, Y, now.k + 1));
visited[X][Y] = now.k + 1;
}
}
}
bw.write(String.valueOf(visited[n - 1][n - 1]));
bw.flush();
}
static class Pair {
int x;
int y;
int k;
public Pair(int x, int y, int k) {
this.x = x;
this.y = y;
this.k = k;
}
}
}
오늘의 회고
BFS 탐색에 다익스트라를 적용하면 해결할 수 있는 문제였다.