백준 4179 (불!)

불!

 

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

 

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

 

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

---

계속 7%에서 틀려서 여러번 반례 확인하고 풀었다.

가장 중요한건 불을 이동한 후 지훈이를 움직이는 것

각각 스택에 담아서 bfs 처럼 풀었다. 불이 번지고 불이 없는 곳으로 움직이고를 반복.

몇가지 틀린 경우는 처음 바로 탈출할 수 있는 경우, 여러 인덱스가 틀린 경우들이었다. 

 

'''
불!

'''
from sys import stdin
input = stdin.readline

R, C = map(int,input().split())

maps = []
visit = [[0]*C for _ in range(R)] 
fires = []

dirs = [(-1,0),(0,1),(1,0),(0,-1)]

# 초기화 작업
# 불, 지훈이 위치
for i in range(R):
    sub = list(input().strip())

    if "J" in sub:
        index = sub.index("J")
        J_idx = (i,index,0)
        visit[i][index] = 1
    
    for j in range(C):
        if "F" == sub[j]:
            fires.append((i,j))
    
    maps.append(sub)

q = [J_idx]

answer = -1

# 너비 탐색
def bfs():
    global answer, q, fires
    # 민규 위치
    while q:
        # 불 이동
        next_fires = []
        while fires:
            fire = fires.pop()
            for dir in dirs:

                if 0 <= fire[0]+dir[0] < R and 0 <= fire[1]+dir[1] < C:

                    if maps[fire[0]+dir[0]][fire[1]+dir[1]] == ["#","F"]:
                        continue
                    elif maps[fire[0]+dir[0]][fire[1]+dir[1]] in ["J","."]:
                        maps[fire[0]+dir[0]][fire[1]+dir[1]] = "F"
                        next_fires.append([fire[0]+dir[0],fire[1]+dir[1]])

        fires = next_fires[:]

        # 민규 이동
        next_q = []
        while q:
            now_x, now_y, cnt = q.pop()
            # 가장 자리 도착
            if now_x in [0,R-1] or now_y in [0,C-1]:
                answer = cnt
                return

            for dir in dirs:

                if 0 <= now_x+dir[0] < R and 0 <= now_y+dir[1] < C:

                    if visit[now_x+dir[0]][now_y+dir[1]]:
                        continue

                    if maps[now_x+dir[0]][now_y+dir[1]] == ["#","F"]:
                        continue
                    elif maps[now_x+dir[0]][now_y+dir[1]] == ".":
                        maps[now_x+dir[0]][now_y+dir[1]] = "J"
                        next_q.append([now_x+dir[0],now_y+dir[1],cnt+1])
                        visit[now_x+dir[0]][now_y+dir[1]] = cnt + 1

        q = next_q[:]

bfs()

if answer != -1:
    print(answer+1)
else:
    print("IMPOSSIBLE")