[백준 5427] 불(파이썬)

https://www.acmicpc.net/problem/5427

5427번: 불

의외로 이 문제로 헤메는 사람이 많고

저 역시나 제법 오랜 시간 뻘짓했다가 풀었습니다.

 

 

예전에 이 문제와 유사하게

밖으로 나가는 경우를 구하는 문제가 있었습니다.

해당 문제의 경우처럼

전체 크기를 h+2 x w+2로 해줬습니다.

기존 입력한 거에서

['.']*(w+2)행을 위 아래로 추가

각 열 앞뒤에 '.'을 추가해줬습니다.

그럼 사람의 x,y좌표가 0or h+1 0 or w+1이면 탈출.

 

그런데 제출하고 한동안 25%를 넘기지 못했습니다.

반례를 찾아서 직접 생각해보니

'불이 번지는 경우'가 문제였습니다.

불이 번지는 범위를

0~h+2 0~w+2로 넣었더니

이렇게되면 건물 밖으로 불이 번져서

다시 건물 안으로 들어오는 경우였습니다.

해당 반례를 찾은 덕분에 문제를 풀 수 있었습니다.

 

import sys
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]


def inside(x,y):
    if x<1 or x>=h+1 or y<1 or y>=w+1:
        return False

    return True

def bfs(sx,sy):
    global answer
    global fire
    q=deque()
    q.append((sx,sy))
    fi=deque()
    visited=[[False]*(w+2) for _ in range(h+2)]
    visited[sx][sy]=True
    f_visited=[[False]*(w+2) for _ in range(h+2)]
    for fx,fy in fire:
        fi.append((fx,fy))
        f_visited[fx][fy]=True

    time=0
    #불이 먼저 퍼지는 걸로 생각하자
    while q:
        flag=False
        #1. 먼저 불이 번짐
        tmp_fire=set()
        for _ in range(len(fi)):
            fx,fy=fi.popleft()

            for d in range(4):
                nx=fx+dx[d]
                ny=fy+dy[d]
                #불 범위조심....
                #탈출을 위해 양싸이드로 2씩 추가했지만
                #불은 저 밖으로 나가면 안된다.
                #저 밖으로 나간다면 건물 밖으로 나가는 경우이므로
                if inside(nx,ny):
                    if not f_visited[nx][ny] and room[nx][ny]!='#':
                        f_visited[nx][ny]=True
                        tmp_fire.add((nx,ny))
        tmp_move=set()
        for _ in range(len(q)):
            gx,gy=q.popleft()
            if gx==0 or gx==h+1 or gy==0 or gy==w+1:
                answer=min(answer,time)
                flag=True

                break

            for d in range(4):
                nx=gx+dx[d]
                ny=gy+dy[d]

                if 0<=nx<h+2 and 0<=ny<w+2:
                    if not visited[nx][ny] and room[nx][ny]!='#' and not f_visited[nx][ny]:
                        visited[nx][ny]=True
                        tmp_move.add((nx,ny))
        if flag:
            break
        if not tmp_move:
            break

        for px,py in tmp_move:
            q.append((px,py))
        for fx,fy in tmp_fire:
            fi.append((fx,fy))
        time+=1

T=int(input())
for _ in range(T):
    answer=sys.maxsize
    w,h=map(int,input().split())
    room=[['.']*(w+2)]
    fire=[]
    sx,sy=-1,-1
    ex,ey=-1,-1
    for i in range(h):
        room.append(list('.' + input().strip() + '.'))

    room.append(['.']*(w+2))

    for x in range(1,h+1):
        for y in range(1,w+1):
            if room[x][y]=='@':
                sx,sy=x,y
                room[x][y]='.'
            elif room[x][y]=='*':
                fire.append((x,y))



    bfs(sx,sy)

    if answer==sys.maxsize:
        print("IMPOSSIBLE")
    else:
        print(answer)

 

이외에 불을 번지는 부분에서

좀 막히신 분들이 많으신 것 같았습니다.

아이디어는 떠올리기 괜찮은데

사소한 것들이 삐걱대기 쉬운 문제로

공부소재로 왕 좋은 문제입니다.