BOJ] 4179. 불!
https://www.acmicpc.net/problem/4179
4179번: 불!
문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간
www.acmicpc.net
기본적으로 BFS알고리즘을 적용하지만, 한번 더 생각이 필요!
보통 2가지 방법으로 접근하는 것 같다.
- 불 한번 퍼지고, 사람한번 움직이기(갈수있는 곳으로) 의 과정을 계속 진행하여 탈출하기
- 불이 모든 맵에 퍼지는 시간을 기록하고 난 뒤, 사람을 움직이기.
처음 풀때는 1번을 생각하지만 1번이 생각은 떠올리기 쉬웠지만 구현에 살짝 까다로움을 겪음
2번은 바로 떠올리지는 못했던 방법인데, 직관적이고 단계별로 푸는 느낌이라 실수..한것을 제외하면 평이하였음
굉장히 비슷한 문제(사실상 똑같음)로는 정올의 '화염에서 탈출' 문제가 있다.
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=30
나는 이 '화염에서 탈출'문제를 1번 방법으로 풀었고, 백준의 불! 문제는 2번 방법으로 풀었당
.
.
2번 방법을 조금 더 설명해보자면.
- 불먼저 퍼뜨림.
- 불이 전부 퍼지는데 걸리는 시간을 기록.
- 불이 퍼지는게 걸리는 시간을 기록해둔 map을 가지고, 내가 움직일 수 있는지 여부를 결정
(불이 먼저 퍼진 상태여야 하므로 부등호 주의) - (놓쳤던 부분 - 불이 퍼지지 않았을 때 시간은 0이었는데, 등호처리때문에 바로 continue(못간다는 판단)을 해버렸당. 0 아닐때 조건을 && 산으로 추가해서 해결
.
혹시 이 문제를 풀때, 테스트 케이스가 분명 맞는데 틀렸습니다가 뜬다면 아래 주소로 가서 테스트케이스를 확인해보면 좋다!
http://acm.student.cs.uwaterloo.ca/~acm00/090613/data/
이 사이트에 들어가서 , 앞에 B라고 적혀있는 데이터들을 모두 돌려보면 된다.
예를 들어, B.0.dat는 테스트케이스, B.0.diff는 정답을 의미한다.
.
.
그럼 이만 즐거운 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
|
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class bj_4179_불 {
static class POS{
int r;
int c;
int time;
public POS(int r, int c, int time) {
this.r = r;
this.c = c;
this.time = time;
}
public POS(int r, int c) {
this.r = r;
this.c = c;
}
}
static int R;
static int C;
static int[][] map;
static boolean[][] visited;
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
static Queue<POS> fire;
static Queue<POS> jihoon;
static int res = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
map = new int[R+2][C+2];
visited = new boolean[R+2][C+2];
fire = new LinkedList<POS>();
jihoon = new LinkedList<POS>();
bound();
for(int i=1; i<R+1; i++) {
String str = sc.next();
for(int j=0; j<str.length(); j++) {
char c = str.charAt(j);
if(c=='#') map[i][j+1] = -9;
if(c=='F') {
map[i][j+1] = 1;
visited[i][j+1]=true;
fire.add(new POS(i,j+1,0));
}
if(c=='J') jihoon.add(new POS(i, j+1, 1));
}
}
fire_bfs();
visited = new boolean[R+2][C+2];
escape_bfs();
if(res==Integer.MAX_VALUE) System.out.println("IMPOSSIBLE");
else System.out.println(res);
}//end main
static void fire_bfs() {
while(!fire.isEmpty()) {
POS p = fire.poll();
for(int i=0; i<4; i++) {
int nr = p.r + dr[i];
int nc = p.c + dc[i];
//벽이든, 바깥범위든 음수니까 continue.
if(map[nr][nc]<0) continue;
if(visited[nr][nc]) continue;
visited[nr][nc] = true;
map[nr][nc] = p.time+1;
fire.add(new POS(nr,nc,p.time+1));
}
}//end while
}//end fire_bfs method
static void escape_bfs() {
while(!jihoon.isEmpty()) {
POS p = jihoon.poll();
visited[p.r][p.c]=true;
for(int i=0; i<4; i++) {
int nr = p.r + dr[i];
int nc = p.c + dc[i];
//탈출
if(map[nr][nc]==-1) {
res = Math.min(res, p.time);
continue;
}
//벽이면 빠끄
if(map[nr][nc]==-9) continue;
//불난곳 빠끄
if(visited[nr][nc]) continue;
// 불이 안퍼졌을때 고려해줘야해. map이 0일때 ㅠㅠㅠㅠ
if(map[nr][nc] !=0 && p.time >= map[nr][nc]) continue;
visited[nr][nc]=true;
jihoon.add(new POS(nr,nc,p.time+1));
}
}
}
static void bound() {
//맨위, 맨아래 초기화
for(int i=0; i<C+2; i++) {
map[0][i] = -1;
map[R+1][i] = -1;
}
//좌 ,우 초기화
for(int i=0; i<R+2; i++) {
map[i][0] = -1;
map[i][C+1] = -1;
}
}
}
|
cs |
'Algorithm > BOJ' 카테고리의 다른 글
| BOJ] 14502. 연구소 (0) | 2020.01.28 |
|---|---|
| BOJ] 2805. 나무 자르기 (0) | 2019.10.05 |
| BOJ] 16283. Farm (0) | 2019.10.01 |
| BOJ] 2579. 계단오르기 (0) | 2019.09.25 |
| BOJ] 1003. 피보나치 함수 (0) | 2019.09.24 |