반응형
https://www.acmicpc.net/problem/9376
처음 접근햇던 방식은 죄수 두명을 각각 큐에 넣어서 탈출할수 있는 경로를 구하고 그경로를 가지고 각각 대조햇을때 겹치는 부분을 제거하는식으로 구할려고 하였다. 하지만 이러한경우 너무많은 case로 인해서 시간초과가 난다.
문제를 풀기위해서는 아이디어가 필요하다. map을 N+2 M+2 크기로 잡아서 외벽에도 공간이 있다고 한다면
바깥족에서 접근하는 사람 1, 죄수 2명 총 3사람을 가지고 BFS를 이용해서 map에 최단경로를 만들수가있다.
이렇게 3명에대한 최단경로를 가지고 전부다를 sum 햇을때를 생각해보자. 죄수 세명이 문을 열어 탈출할수 있는 최단경로는 세며의 사람이 각각 문을 열면서 갈때 어느 하나의 문에서 만날때가 최단으로 문을여고 탈출하는 경우다.
따라서 각각의 sum을 구하고 $ 지점에서 최단값을 찾으면된다. 이때 답은 -2를 해주면된다 세명이 마지막 겹치는 점에서 문을 열기때문이다.
그러면 문을 안열고 나갈수도 있지않은가?? 이러한경우는 0,0 지점에 값을 비교해주면된다. 죄수세명이 #을 하나도 거치지않고 나갓다면 0,0 인지점에서 값을 비교하면 되기때문이다
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
|
package day0304;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class B9376 {
static int T;
static int N, M;
static char[][] map;
static int[][] digit;
static int[][] sumDigit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N + 2][M + 2];
sumDigit = new int[N + 2][M + 2];
for (int i = 0; i < N + 2; i++) {
Arrays.fill(map[i], '.');
}
for (int i = 1; i <= N; i++) {
char c[] = br.readLine().toCharArray();
for (int j = 1; j <= M; j++) {
map[i][j] = c[j - 1];
}
}
BFS(0, 0);
for (int i = 1; i <= N; i++) {
for (int j = 1; j < M; j++) {
if (map[i][j] == '$')
BFS(i, j);
}
}
int Answer = sumDigit[0][0];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if(map[i][j]=='#') {
}
}
}
System.out.println(Answer);
}
}
static class Pair {
int y;
int x;
int w;
public Pair(int y, int x, int w) {
super();
this.y = y;
this.x = x;
this.w = w;
}
}
static int dy[] = { 1, -1, 0, 0 };
static int dx[] = { 0, 0, 1, -1 };
static void BFS(int y, int x) {
digit = new int[N + 2][M + 2];
for (int i = 0; i < N + 2; i++) {
}
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(y, x, 0));
digit[y][x] = 0;
while (!q.isEmpty()) {
Pair tmp = q.poll();
for (int d = 0; d < 4; d++) {
int ny = tmp.y + dy[d];
int nx = tmp.x + dx[d];
if (ny < 0 || nx < 0 || ny >= N + 2 || nx >= M + 2)
continue;
if (map[ny][nx] == '*')
continue;
int next = (map[ny][nx] == '#') ? 1 : 0;
next += tmp.w;
if (digit[ny][nx] > next) {
digit[ny][nx] = next;
q.add(new Pair(ny, nx, next));
}
}
}
for (int i = 0; i < N + 2; i++) {
for (int j = 0; j < M + 2; j++) {
if(map[i][j]=='*')continue;
sumDigit[i][j] += digit[i][j];
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'ProgramSoliving' 카테고리의 다른 글
벨만포드 알고리즘 : 백준 11657 ( 타임머신) (0) | 2020.03.08 |
---|---|
백준 : 1039 JAVA (0) | 2020.03.07 |
백준 : 2933 JAVA (0) | 2020.03.03 |
백준 : 10830 (0) | 2020.03.02 |
백준 : 11401 (0) | 2020.03.02 |