[백준 #5427, Python] 불

[풀이]

사실 풀었다고 하면 안됨,,거의 인터넷과 함께 집단지성 수준 이였다.. 이 문제는 정말 제목 그대로 나에게 불을 지펴줬는데 ^^,,,

1. 처음에는 상근이의 첫 시작 위치에 불이 도착해야지만 상근이가 출발이 가능하다고 생각했었음 ^^ 아니네

=> 그래서 이거 처리가 진짜 골때려서 어케 하지? 하는 생각에 3일정도를 날려보냈음

2. 한 차례에 어떻게 하면 bfs를 중단하고, 불 - 상근이- 불 을 왔다갔다 하지? 하는게 문제

2번의 해결책은 queue의 길이를 지정해줘서, 처음 들어간 큐만큼만 돌아가게 해주면 해결 되었다.

그런데 이제 다음에, 상근이의 bfs를 한번 돌고 => 다시 불을 지피고 => 상근이로 넘어가서 돌아야하는데, 상근이가 안돌아가는 것이다,,!!!!! 이거는 while q로 크게 묶어서 상근이는 큐 안에 좌표들이 있으면 계속 반복하게 해줘야 했다.

진짜 구조가 어려운 것 같다.. 사실 아직도 이해는 잘 안돼.. 

그리고 최종적으로 시간 초과가 계속 발생했었는데 => 이는 분기처리를 안해줘서 이미 불이 지펴진데랑, 방문했던 곳이랑 겹쳐지면서 계속 검사되서 시간 초과가 발생한 것 같다.

visit로 또 처리하자니 너무 싫어서 구글링으로 찾은 방법이 아직 방문하지 않는 지역은 거리가 0 이다는 것을 활용해서, 길인지를 확인하는 if문에 D[nr][nc] == 0으로 방문 확인도 해주었다.

 

from sys import stdin
from collections import deque
def bfs():
    while q:
        q_len = len(q)
        for j in range(q_len):
            r,c = q.popleft()
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0<=nr<N and 0<=nc<M:
                    if maps[nr][nc] == '.' and D[nr][nc] == 0:
                        q.append((nr,nc))
                        D[nr][nc] = D[r][c] + 1
                elif 0>nr or nr==N or 0>nc or M==nc:
                    print(D[r][c]+1)
                    return
        fire()
    print("IMPOSSIBLE")
    return

def fire():
    fire_len = len(fireq)
    for j in range(fire_len):
        r,c = fireq.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0<=nr<N and 0<=nc<M:
                if maps[nr][nc] == '.':
                    fireq.append((nr,nc))
                    maps[nr][nc] = '*'


T = int(stdin.readline())
for _ in range(T):
    M,N = map(int,stdin.readline().split())
    fireq = deque([])
    q = deque([])
    maps= []
    D = [[0]*M for _ in range(N)]
    for r in range(N):
        tmp = list(map(str,stdin.readline().strip()))
        for c in range(M):
            if tmp[c] == '*':
                fireq.append((r,c))
            elif tmp[c] == '@':
                q.append((r,c))
                tmp[c] = '.'
        maps.append(tmp)
    dr = [-1,1,0,0]
    dc = [0,0,-1,1]
    fire()
    bfs()