사실 첨부터 풀어낼 자신이 없었기 때문에 강의 먼저 듣고 풀었다(플레에 기 죽어버림)
이 문제를 풀면서 새로 안 사실은
가중치가 시간처럼 움직이면 전부 증가하는 (가중치가 전부 동일한)게 아닌 문 연 횟수처럼 다른 상황에서는
1. 그래프를 확장해도 최단경로(찾고자 하는 최솟값)는 변하지 않는다.
2. 가중치가 0과 1일땐, 0-1BFS라는 기법을 사용할 수 있다.
또한 이 문제에서 생각해야할 몇가지는
1. 시작점이 한개 이상이다 (죄수가 두명임)
2. 여기서 그래프를 확장하면 , 죄수는 감옥을 빠져나가 돌아다니다 보면 반드시 만난다는 점이다. (만나게하기 위해 그래프를 확장하는것)
그러면 두 죄수가 탈출하는 상황 두가지를 생각해볼 수 있다.
1) 감옥안에서 탈출하다가, 두 죄수가 만나서 같은 경로로 탈출한다.
2) 두 죄수가 다른경로로 탈출하다가 밖에서 만난다.
이러한 상황은 1번 죄수가 탈출하면서 문 연 횟수 + 2번 죄수가 탈출하면서 문 연 횟수 + 1,2번 죄수가 탈출하다 만나서 같이 탈출하면서 문 연 횟수(0이 될 수도 있음) 로 일반화 할수 있다.
따라서 최솟값을 구하기 위해서는
1번 죄수 시작으로 문 연 횟수를 전부 구함
2번 죄수 시작으로 문 연 횟수를 전부 구함
감옥 밖에서 시작으로 문 연 횟수를 전부 구함
한 다음
최소가 되는 지점을 구하면 된다.
여기서 가중치가 0 (.인 지점을 지날 때 ) , 1(문을 열때) 이 존재하므로 데크를 이용하여 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
package algorithm;
import java.util.*;
import java.io.*;
public class B9376 {
static int[][] count1;
static int[][] count2;
static int[][] count3;
static boolean[][] visit;
static char[][] board;
static int H;
static int W;
static int[] dx = { -1, +1, 0, 0 };
static int[] dy = { 0, 0, +1, -1 };
public static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static boolean check(int x, int y) {
return x >= 0 && x < H && y >= 0 && y < W && board[x][y] != '*';
}
public static void bfs(int[][] cnt, Point start) {
Deque<Point> que = new LinkedList<Point>();
que.add(start);
visit[start.x][start.y] = true;
cnt[start.x][start.y] = 0;
while (!que.isEmpty()) {
Point tmp = que.poll();
int x = tmp.x;
int y = tmp.y;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (check(nx, ny)) {
if (!visit[nx][ny]) {
if (board[nx][ny] == '#') {
// 문을 열고 가야 함
cnt[nx][ny] = cnt[x][y] + 1;
visit[nx][ny] = true;
que.addLast(new Point(nx, ny));
} else {
visit[nx][ny] = true;
que.addFirst(new Point(nx, ny));
cnt[nx][ny] = cnt[x][y];
}
}
}
}
}
}
public static void print(int[][] count) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
System.out.print(count[i][j] + " ");
}
System.out.println();
}
System.out.println();
return;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
String[] inputs = br.readLine().split(" ");
H = Integer.parseInt(inputs[0]) + 2;
W = Integer.parseInt(inputs[1]) + 2;
count1 = new int[H][W];
count2 = new int[H][W];
count3 = new int[H][W];
board = new char[H][W];
boolean first = false;
int x1 = 0;
int y1 = 0;
int x2 = 0;
int y2 = 0;
for (int i = 1; i < H - 1; i++) {
String input = br.readLine();
char[] arrs = input.toCharArray();
for (int j = 1; j < W - 1; j++) {
board[i][j] = arrs[j - 1];
if (board[i][j] == '$') {
if (!first) {
first = true;
x1 = i;
y1 = j;
} else {
x2 = i;
y2 = j;
}
}
}
}
for(int i = 0 ;i<H ; i++ ) {
for(int j = 0 ; j<W ; j++) {
count1[i][j] = -1;
count2[i][j] = -1;
count3[i][j] = -1;
}
}
visit = new boolean[H][W];
bfs(count1, new Point(x1, y1));
visit = new boolean[H][W];
bfs(count2, new Point(x2, y2));
visit = new boolean[H][W];
bfs(count3, new Point(0, 0));
// print(count1);
// print(count2);
// print(count3);
int minx = 0 ; int miny = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if(count1[i][j] == -1 || count2[i][j] == -1 || count3[i][j] == -1) continue;
else {
int sum = count1[i][j] + count2[i][j] + count3[i][j];
if (board[i][j] == '#') {
sum -= 2;
}
if(min > sum) {
min = Math.min(min, sum);
minx = i ; miny = j;
}
}
}
}
System.out.println(min);
// System.out.println(minx+" , "+miny);
}
}
}
|
cs |
이문제 진짜 어렵다..
근데 배울건 많아서 두고두고 보려고 블로그에 글남긴다.