[백준/BOJ][Python] 4179번 불!

[백준/BOJ][Python] 4179번 불!

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

4179번: 불!

 

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

예제 입력 1 복사

4 4
####
#JF#
#..#
#..#

예제 출력 1 복사

3

---

생각한 과정

정말 눈물 나는 성공이다....

 

문제를 보고 떠오른 생각은 불 먼저 BFS 돌면서 불 난 시간을 저장한 후에,
지훈이가 BFS를 돌면서 불 나는 시간 전에 지나간다면 OK 라고 생각했다.

 

결론적으로 이 생각은 맞았다.

 

근데 고려해야 될 게 많았다.

1) 불이 움직이지 못하는 경우

2) 탈출할 때는 그래프 범위를 벗어나야 함

3) 불이 여러 곳에서 날 수 있음

4) 불이 벽에 갇히면 주변으로 안 퍼질 수도 있음

 

계속 안됐던 반례..

4 4
###F
#J.#
#..#
#..#
    
# Answer : 3

7 7
#######
#J###F#
#.....#
#.#.#.#
#.#.#.#
F.#.#.#
#####.#

# Answer : IMPOSSIBLE

 

queue_J와 queue_F는 각각 지훈이와 불의 위치를 저장하기 위한 큐

visit_J와 visit_F는 각각 지훈이와 불이 해당 위치를 방문했는지 여부를 저장하는 리스트

 

불이 번지는 시간을 계산하기 위해 불의 위치를 저장하는 큐인 queue_F에서 하나씩 꺼내면서 상하좌우로 인접한 공간 중 방문하지 않은 공간을 찾아 방문처리

불이 번지는 시간을 저장하는 visit_F 리스트도 업데이트

 

queue_J에서 지훈이의 위치를 하나씩 꺼내서 상하좌우로 이동

이 때 불이 번지기 전에 지훈이가 도달한 공간일 경우에만 방문처리를 하고 visit_J에 저장

불이 있는 곳에 도달한 경우에는 불이 있는 곳에 도달한 시간 visit_F와 현재 위치까지의 거리 visit_J[x][y]를 비교하여 불이 있는 곳에 더 늦게 도착하는 경우는 지나갈 수 없기 때문에 무시

 

마지막으로 지훈이가 탈출할 수 있는지를 검사

범위 밖에 도달하는 순간 해당 위치의 visit_J 값에 1을 더한 값을 출력하고 프로그램을 종료

만약 지훈이가 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력

---

코드

import sys
from collections import deque
input = sys.stdin.readline

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

R, C = map(int, input().split())
graph = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue_J, queue_F = deque(), deque() # BFS 하기 위한 Queue
visit_J, visit_F = [], [] # 방문처리 할 리스트

for i in range(R):
    visit_J.append([0]*C) # 방문처리 0은 not visited, 1은 visited
    visit_F.append([0]*C)
    graph.append(list(input().rstrip())) # rstrip() 쓰면 맨 뒤에 있는 개행문자 제거됨

temp = [] # 처음 주어질 때 F 였던 애들 1로 만들기 위해서(반복문 돌다보면 중복돼서 숫자 계속 늘어나는 오류 해결 위해서)
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'J':
            queue_J.append((i, j))
        if graph[i][j] == 'F':
            queue_F.append((i, j))
            temp.append([i, j]) # 처음 주어질 때 F인 애들 append

# 불이 번지는 시간을 visitF에 저장
while queue_F:
    x, y = queue_F.popleft()
    for i in range(4): # 상하좌우 돌기
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C: # 범위 안에 있으면
            if visit_F[nx][ny] == 0 and graph[nx][ny] != '#': # 방문하지 않았고 벽이 아니면
                visit_F[nx][ny] = visit_F[x][y] + 1 # time + 1
                queue_F.append((nx, ny))

# 반복문 돌다보면 중복돼서 숫자 계속 늘어나는 오류 해결 위해
for i in range(len(temp)): 
    a = temp[i][0]
    b = temp[i][1]
    visit_F[a][b] = 1

# 불에 번지는 시간에 따른
# 지훈이의 대피 시간 계산
while queue_J:
    x, y = queue_J.popleft()
    for i in range(4): # 상하좌우
        nx = x + dx[i]
        ny = y + dy[i]
        if not (0 <= nx < R and 0 <= ny < C): # 범위 밖이므로 탈출 성공
            print(visit_J[x][y] + 1)
            sys.exit(0) # 바로 프로그램 종료

        if visit_J[nx][ny] == 0 and graph[nx][ny] != "#": # 방문하지 않았고 벽이 아닐 때
            if visit_F[nx][ny] == 0 or visit_J[x][y]+1 < visit_F[nx][ny]: # 불이 난 적 없거나 불이 오기 전에 갈 수 있는 곳이라면
                visit_J[nx][ny] = visit_J[x][y]+1
                queue_J.append((nx, ny))


print("IMPOSSIBLE")