[백준 5427] 불 (C++/Python)

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 있냐없냐이다.