[백준 4179] 불! (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_NUM 1002
using namespace std;

string arr[MAX_NUM];
int visited[MAX_NUM][MAX_NUM];
queue<pair<int, int>> jq;
queue<pair<int, int>> fq;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int r, c;
	cin >> r >> c;

	for (int i = 0; i < r; i++) {
		cin >> arr[i];

		for (int j = 0; j < c; j++) {
			if (arr[i][j] == 'J') {
				jq.push({ i,j });
			}
			else if (arr[i][j] == 'F') {
				fq.push({ i,j });
				visited[i][j] = 1;
			}
		}
	}

	// 불을 퍼트린다.
	while (!fq.empty()) {
		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 >= r || ny < 0 || ny >= c) continue;

			if ((arr[nx][ny] == '.' || arr[nx][ny] == 'J') && visited[nx][ny] == 0) {
 				visited[nx][ny] = visited[x][y] + 1;
				fq.push({ nx,ny });
			}
		}
	}

	// 지훈이 도망간다.
	int ans = 987654321;
	visited[jq.front().first][jq.front().second] = 1;
	while (!jq.empty()) {
		int x = jq.front().first;
		int y = jq.front().second;
		jq.pop();

		if (x == 0 || x == r - 1 || y == 0 || y == c - 1) {
			ans = visited[x][y];
			break;
		}

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;

			if ((arr[nx][ny] == '.' || arr[nx][ny] == 'J') && (visited[nx][ny] == 0 || visited[x][y] + 1 < visited[nx][ny])) {
				visited[nx][ny] = visited[x][y] + 1;
				jq.push({ nx,ny });
			}
		}
	}

	(ans != 987654321) ? cout << ans : cout << "IMPOSSIBLE";

	return 0;
}

 

 

 

Python)

import sys
from collections import deque
read = sys.stdin.readline

r, c= map(int, read().rstrip().split())

arr = [read().rstrip() for _ in range(r)]
visited = [ [0] * c for _ in range(r)]
jq = deque()
fq = deque()
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(r):
    for j in range(c):
        if arr[i][j] == 'J':
            jq.append((i,j))
        elif arr[i][j] == 'F':
            fq.append((i,j))
            visited[i][j] = 1

while fq:
    x, y = fq.popleft()

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            continue

        if (arr[nx][ny] == '.' or arr[nx][ny] == 'J') and visited[nx][ny] == 0:
            visited[nx][ny] = visited[x][y] + 1
            fq.append((nx,ny))

ans = -1
visited[jq[0][0]][jq[0][1]] = 1

while jq:
    x, y = jq.popleft()

    if x == 0 or x == r-1 or y == 0 or y == c-1:
        ans = visited[x][y]
        break

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            continue

        if (arr[nx][ny] == '.' or arr[nx][ny] == 'J') and (visited[nx][ny] == 0 or visited[x][y] + 1 < visited[nx][ny]):
            visited[nx][ny] = visited[x][y] + 1
            jq.append((nx,ny))

print(ans if ans != -1 else "IMPOSSIBLE")