문제 URL : https://www.acmicpc.net/problem/5427
문제 접근법:
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
|
#include <iostream>
#include <queue>
using namespace std;
char map[1000][1000];
int w, h;//가로 세로
int sy, sx;//출발점
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 }; //방향
int visit[1000][1000];
bool isrange(int y, int x){//범위 안에 있는지 확인
if (0 <= y&&y < h && 0 <= x&&x < w)
return true;
return false;
}
struct coordinate{
int y, x, cost;
coordinate(int y, int x, int cost) :y(y), x(x), cost(cost){}
};
void init(){
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
visit[i][j] = 0;
}
}
}
int bfs(vector<pair<int, int>> &fire){
queue<coordinate> q, fq;//상근이가 이동하기위한 자료형구조 q 불이 번지기위한 fq
q.push({ sy, sx, 1 });
visit[sy][sx] = 1;
for (int i = 0; i < fire.size(); i++)//불의좌표를 fq에넣음
fq.push({ fire[i].first, fire[i].second, 1 });
while (!fq.empty() || !q.empty())//
{
int fqsize = fq.size();//불을 먼저 퍼트리기
while (fqsize--){
int y = fq.front().y;
int x = fq.front().x;
fq.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && map[ny][nx] == '.')//빈공간만 불을 번지게함
{
fq.push({ ny, nx, 1 });
map[ny][nx] = '*';
}
}
}
int qsize = q.size();//불이 번졌다면 상근이를 움직이게함
while (qsize--){
int y = q.front().y;
int x = q.front().x;
int cost = q.front().cost;
if (y == h - 1 || y == 0 || x == w - 1 || x == 0)//도착지점
return cost;
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && map[ny][nx] == '.'&&visit[ny][nx] == 0)
{
q.push({ ny, nx, cost + 1 });
visit[ny][nx] = 1;
}
}
}
}
return -1;//실패
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test;
cin >> test;
while (test--){
cin >> w >> h;
vector<pair<int, int>> fire;
init();
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> map[i][j];
if (map[i][j] == '@')//상근이가 있는위치를 저장해주고 그자리를 .으로 바꿈
{
sy = i;
sx = j;
map[i][j] == '.';
}
else if (map[i][j] == '*'){//불의 좌표들을 벡터로 저장
fire.push_back({ i, j });
}
}
}
int result = bfs(fire);
if (result == -1)
cout << "IMPOSSIBLE\n";
else
cout << result << "\n";
}
}
|
cs |
코드를 보면 직관적으로 바로 이해하실수 있을거라 생각합니다.
이해가 안되는점이나 궁금한점이 있다면 언제든지
댓글을 달아주세요 ㅎㅎ
'백준' 카테고리의 다른 글
| 백준 1890 점프 (0) | 2020.07.22 |
|---|---|
| 백준 17830 이진수씨의 하루 일과 (0) | 2020.07.22 |
| 백준 2630 색종이 만들기 (0) | 2020.07.20 |
| 백준 1992 쿼드트리 (0) | 2020.07.20 |
| 백준 1456 거의 소수 (0) | 2020.07.20 |
