백준 5427 [불] 파이썬

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

 

아이디어는 바로 생각났으나, 시간 초과로 애를 먹었다.

#백준 5427 불
import sys
from collections import deque
dr=[0,0,1,-1] #행 이동
dc=[1,-1,0,0] #열 이동
T=int(sys.stdin.readline()) #테스트 케이스 입력처리
for _ in range(T):
    q=deque([]) #덱 이용(시간단축)
    is_success=False #성공 여부 확인
    col,row=map(int,sys.stdin.readline().rstrip().split())
    field=[[0] *col for _ in range(row)] #필드생성
    for i in range(row):
        line=list(map(str,sys.stdin.readline()))
        for j in range(col):
            if line[j]=='#': #벽이면
                field[i][j]=1000000 #벽=1000000으로 설정
            elif line[j]=='.': #빈공간이면
                field[i][j]=-1
            elif line[j]=='*': #불이면
                q.append([i,j,'F']) # 번지는것을 구분하기 위해 뒤에 불이면 'F' 붙임
                field[i][j]=1000000 #불==벽==1000000
            elif line[j]=='@': #사람이면
                start_r=i
                start_c=j
                field[i][j]=0

    q.append([start_r,start_c,'S']) #번지는것을 구분하기 위해 사람이면 뒤에 'S' 붙임
    while q:
        r,c,k=q.popleft()
        for i in range(4):
            R=r+dr[i]
            C=c+dc[i]
            if k=='S': #사람이면
                if 0<=R<row and 0<=C<col: #사람 이동 처리
                    if field[R][C]==-1:
                        q.append([R,C,'S'])
                        field[R][C]=field[r][c]+1
                else: #성공하면
                    is_success=True
                    print(field[r][c]+1)
                    break #탈출
            else: #불이면
                if 0<=R<row and 0<=C<col and field[R][C]==-1: #불 번짐 처리
                    q.append([R,C,'F'])
                    field[R][C]=1000000
        if is_success==True:
            break
    if not is_success: #탈출못하는 경우
        print("IMPOSSIBLE")

파이썬 리스트가 아닌 덱을 이용하여 시간단축하였다.