4179번: 불!
문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간
www.acmicpc.net
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int R, C;
string str;
int maze[1000][1000]; // 0 : 무, 1 : 지훈 기방문, 2 : 불, 3 : 벽
enum TILE{NONE, VST, FIRE, WALL};
queue<pair<int, int>> jq, fq;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// 입력 시 모든 문자에 대한 처리(maze에 표시/별도 자료구조) 완료할 것
cin >> R >> C;
for (int r = 0; r < R; ++r) {
cin >> str;
for (int c = 0; c < C; ++c) {
switch (str[c]) {
case 'J':
maze[r][c] = VST;
jq.push({ r, c });
break;
case 'F':
maze[r][c] = FIRE;
fq.push({ r, c });
break;
case '#':
maze[r][c] = WALL;
break;
}
}
}
// 디버깅 완료
int t = 0;
while (!jq.empty()) {
// 지훈이 이동
int jqs = jq.size();
while (jqs--) {
int r = jq.front().first, c = jq.front().second;
jq.pop();
if (r < 0 || R <= r || c < 0 || C <= c) {
goto out;
}
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc) {
jq.push({ nr, nc });
continue;
}
if (!maze[nr][nc]) {
maze[nr][nc] = VST;
jq.push({ nr, nc });
}
}
}
// 불 확산
int fqs = fq.size();
while (fqs--) {
int r = fq.front().first, c = fq.front().second;
fq.pop();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc) {
continue;
}
if (maze[nr][nc] == FIRE || maze[nr][nc] == WALL) {
continue;
}
maze[nr][nc] = FIRE;
fq.push({ nr, nc });
}
}
// 지훈이가 불에 데였나
jqs = jq.size();
while (jqs--) {
int r = jq.front().first, c = jq.front().second;
jq.pop();
if (maze[r][c] != FIRE) {
jq.push({ r, c });
}
}
++t;
}
cout << "IMPOSSIBLE";
return 0;
out:
cout << t;
return 0;
}불을 먼저 이동하면 // 지훈이가 불에 데였나 부분을 생략할 수 있다.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int R, C;
string str;
int maze[1000][1000]; // 0 : 무, 1 : 지훈 기방문, 2 : 불, 3 : 벽
enum TILE{NONE, VST, FIRE, WALL};
queue<pair<int, int>> jq, fq;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// 입력 시 모든 문자에 대한 처리(maze에 표시/별도 자료구조) 완료할 것
cin >> R >> C;
for (int r = 0; r < R; ++r) {
cin >> str;
for (int c = 0; c < C; ++c) {
switch (str[c]) {
case 'J':
maze[r][c] = VST;
jq.push({ r, c });
break;
case 'F':
maze[r][c] = FIRE;
fq.push({ r, c });
break;
case '#':
maze[r][c] = WALL;
break;
}
}
}
// 디버깅 완료
int t = 0;
while (!jq.empty()) {
// 불 확산
int fqs = fq.size();
while (fqs--) {
int r = fq.front().first, c = fq.front().second;
fq.pop();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc) {
continue;
}
if (maze[nr][nc] == FIRE || maze[nr][nc] == WALL) {
continue;
}
maze[nr][nc] = FIRE;
fq.push({ nr, nc });
}
}
// 지훈이 이동
int jqs = jq.size();
while (jqs--) {
int r = jq.front().first, c = jq.front().second;
jq.pop();
if (r < 0 || R <= r || c < 0 || C <= c) {
goto out;
}
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc) {
jq.push({ nr, nc });
continue;
}
if (!maze[nr][nc]) {
maze[nr][nc] = VST;
jq.push({ nr, nc });
}
}
}
++t;
}
cout << "IMPOSSIBLE";
return 0;
out:
cout << t;
return 0;
}확산은 순서가 중요하다!
