Baekjoon #4179

Baekjoon #4179

1개의 풀이 · Python

문제 원문 보기 ↗

SOLUTION INFO

Python · main.py

main.py
from collections import deque
import sys

def input():
    return sys.stdin.readline().rstrip()

r, c = map(int, input().split())
board = [[-1] * (c+2) for _ in range(r+2)]
visit = [[False] * (c+2) for _ in range(r+2)]
q = deque()
fire_q = deque()
dy = [0, 0, -1, 1]
dx = [-1, 1, 0, 0]

for i in range(1,r+1):
    line = input()
    for j in range(1,c+1):
        if line[j-1]=='#': board[i][j] = 1
        elif line[j-1]=='.': board[i][j] = 0
        elif line[j-1]=='J': 
            board[i][j] = 0
            q.append([i,j])
        elif line[j-1]=='F': 
            board[i][j] = 2
            fire_q.append([i,j])

def check(cur, board):
    y, x = cur
    return board[y][x] == -1

def bfs(q, cnt):
    global r, c
    next_q = deque()
    while q:
        y, x = q.popleft()
        if board[y][x] == 2: continue
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if ny<0 or ny>=r+2 or nx<0 or nx>=c+2: continue
            if board[ny][nx] == 1 or board[ny][nx] == 2: continue
            if visit[ny][nx]: continue
            if check((ny,nx), board):
                return True, next_q
            next_q.append([ny, nx])
            visit[ny][nx] = True
    return False, next_q

def fire_bfs(q):
    global r, c
    next_q = deque()
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if ny<=0 or ny>=r+1 or nx<=0 or nx>=c+1: continue
            if board[ny][nx] == 1 or board[ny][nx] == 2: continue
            next_q.append([ny, nx])
            board[ny][nx] = 2
    return next_q

def solution():
    global q, fire_q
    cnt = 0
    while True:
        cnt += 1
        chk, q = bfs(q, cnt)
        if chk:
            return cnt
        if not q:
            return 'IMPOSSIBLE'
        fire_q = fire_bfs(fire_q)
    return 'IMPOSSIBLE'

print(solution())

SOLUTION DESCRIPTION

풀이 설명

등록된 풀이 설명이 없습니다.