[백준] 4179번 | 불 | Python

---

문제 링크: https://www.acmicpc.net/problem/4179

---

문제

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

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

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

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

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

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

---

입력

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

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

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

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

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

---

출력

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

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

---

내 풀이

지훈이 초기위치 J와 불의 초기위치 F에 대해서 각각 BFS를 진행한다.

각각 미로의 가장자리를 탐색해 불보다 지훈이가 빨리 도착해있다면 그 경우들 중 최소의 경우를 출력하고, 그런 경우가 한 번도 없다면 IMPOSSIBLE을 출력한다.

---

코드

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
temp = input()
[R, C] = temp.split()
R = int(R)
C = int(C)

def BFS(S, maze):
    visit = [[R*C]*C for _ in range(R)]
    q = []
    for x in range(len(S)):
        q.append(S[x])
        visit[S[x][0]][S[x][1]] = 0

    while q:
        [y, x] = q.pop(0)

        for t in range(4):
            new_y = y + dy[t]
            new_x = x + dx[t]

            if new_y > -1 and new_y < R and new_x > -1 and new_x < C and maze[new_y][new_x] != '#':
                if visit[new_y][new_x] == (R*C):
                    visit[new_y][new_x] = visit[y][x] + 1
                    q.append([new_y, new_x])

    return visit

def main():
    maze = []
    Fs = []
    Js = []
    
    for y in range(R):
        temp = input()
        maze.append(temp)
        if 'J' in temp:
            Js.append([y, temp.index('J')])
        
        for x in range(C):
            if 'F' == temp[x]:
                Fs.append([y, x])
    JMap = BFS(Js, maze)
    FMap = BFS(Fs, maze)

    answer = R*C
    for x in range(C):
        if JMap[0][x] < FMap[0][x]:
            answer = min(answer, JMap[0][x])
        if JMap[R-1][x] < FMap[R-1][x]:
            answer = min(answer, JMap[R-1][x])

    for y in range(R):
        if JMap[y][0] < FMap[y][0]:
            answer = min(answer, JMap[y][0])
        if JMap[y][C-1] < FMap[y][C-1]:
            answer = min(answer, JMap[y][C-1])

    if answer == R*C:
        print('IMPOSSIBLE')
    else:
        print(answer + 1)

if __name__ == "__main__":
    main()