1. 조건
- 동서남북
- 벽에 불 못 번진다.
- 상근이는 벽을 통과할 수 없다.
- 불이 옮겨진 칸 또는 붙으려는 칸으로 이동할 수 없다.
ㄴ 불을 먼저 번지게 한 이유
2. 입력
- 1 <= w, h <= 1000
ㄴ 크기가 1x1일수도 있다.
3. 출력
- 테스트케이스가 여러개이므로 엔터 잘 쳐야한다.
4. 반례
3
1 1
@
2 2
..
@.
4 4
....
..@.
....
....
// 정답
// 1
// 1
// 2
C++)
#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_NUM 1002
using namespace std;
string arr[MAX_NUM];
int fire[MAX_NUM][MAX_NUM]; // 불 이동경로
int sang[MAX_NUM][MAX_NUM]; // 상근 이동경로
queue<pair<int, int>> sq; // 불 큐
queue<pair<int, int>> fq; // 상근 큐
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int LetsEscape(int h, int w) {
bool flag = true;
int escapeTime = 0;
while (flag) {
if (fq.empty() && sq.empty())
break;
// 불 먼저 이동
int fqSize = fq.size();
for (int i = 0; i < fqSize; i++) {
int x = fq.front().first;
int y = fq.front().second;
fq.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
// 상근이가 이미 간 곳이라면 굳이 갈 필요가 없다 -> sang[nx][ny] == 0 넣은 이유
if ((arr[nx][ny] == '.' || arr[nx][ny] == '@') &&
(fire[nx][ny] == 0 && sang[nx][ny] == 0)) {
fire[nx][ny] = fire[x][y] + 1;
fq.push({ nx,ny });
}
}
}
// 상근이 탈출중
int sqSize = sq.size();
for (int i = 0; i < sqSize; i++) {
int x = sq.front().first;
int y = sq.front().second;
sq.pop();
// 가장자리이면 탈출!
if (x == 0 || x == h - 1 || y == 0 || y == w - 1) {
escapeTime = sang[x][y];
flag = false;
break;
}
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
// 불 먼저 번지게 하고 상근이가 이동하기 때문에 fire[nx][ny] != 0 이라면
// 무조건 상근이보다 먼저 도착하기 때문에 fire[nx][ny] == 0
// 그리고 이미 간 곳이라면 갈 필요가 없다 -> sang[nx][ny] == 0
if ((arr[nx][ny] == '.' || arr[nx][ny] == '@') &&
(fire[nx][ny] == 0 && sang[nx][ny] == 0)) {
sang[nx][ny] = sang[x][y] + 1;
sq.push({ nx,ny });
}
}
}
}
return escapeTime;
}
void Clear(int h, int w) {
for (int i = 0; i < h; i++) {
fill(fire[i], fire[i] + w, 0);
fill(sang[i], sang[i] + w, 0);
}
while (!sq.empty())
sq.pop();
while (!fq.empty())
fq.pop();
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t, w, h;
cin >> t;
while (t--) {
cin >> w >> h;
for (int i = 0; i < h; i++) {
cin >> arr[i];
for (int j = 0; j < w; j++) {
if (arr[i][j] == '@') {
sq.push({ i,j });
sang[i][j] = 1;
}
else if (arr[i][j] == '*') {
fq.push({ i,j });
fire[i][j] = 1;
}
}
}
// 탈출하자
int ans = LetsEscape(h, w);
(ans != 0) ? cout << ans << "\n" : cout << "IMPOSSIBLE\n";
Clear(h, w);
}
return 0;
}
Python)
import sys
from collections import deque
read = sys.stdin.readline
dx = [1,0,-1,0]
dy = [0,1,0,-1]
t = int(read().rstrip())
def LetsEscape(h, w):
flag = True
escape_time = 0
while flag:
if not fq and not sq:
break
fq_size = len(fq)
for i in range(fq_size):
x, y = fq.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= h or ny < 0 or ny >= w:
continue
if (arr[nx][ny] == '.' or arr[nx][ny] == '@') and (fire[nx][ny] == 0 and sang[nx][ny] == 0):
fire[nx][ny] = fire[x][y] + 1
fq.append((nx,ny))
sq_size = len(sq)
for i in range(sq_size):
x, y = sq.popleft()
if x == 0 or x == h-1 or y == 0 or y == w-1:
flag = False
escape_time = sang[x][y]
break
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= h or ny < 0 or ny >= w:
continue
if (arr[nx][ny] == '.' or arr[nx][ny] == '@') and (fire[nx][ny] == 0 and sang[nx][ny] == 0):
sang[nx][ny] = sang[x][y] + 1
sq.append((nx,ny))
return escape_time
for _ in range(t):
w, h = map(int, read().rstrip().split())
arr = [[] * w for __ in range(h)]
sang = [[0] * w for __ in range(h)]
fire = [[0] * w for __ in range(h)]
sq = deque()
fq = deque()
for i in range(h):
arr[i] = list(read().rstrip())
for j in range(w):
if arr[i][j] == '@':
sq.append((i,j))
sang[i][j] = 1
elif arr[i][j] == '*':
fq.append((i,j))
fire[i][j] = 1
ans = LetsEscape(h, w)
print(ans if ans != 0 else "IMPOSSIBLE")
C++이랑 파이썬 로직은 동일한데 유일한 다른점은 clear 있냐없냐이다.
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 11404] 플로이드 (C++/Java) (0) | 2020.12.08 |
|---|---|
| [백준 3055] 탈출 (C++) (0) | 2020.12.08 |
| [백준 14442] 벽 부수고 이동하기 2 (0) | 2020.12.08 |
| [백준 1865] 웜홀 (0) | 2020.12.08 |
| [백준 11657] 타임머신 (0) | 2020.12.08 |