[정올 1082] 화염에서탈출

문제

재우는 중간계(middle-earth)에서 유명한 용사이다.

 

어느날 사람들에게 부탁 받은 마물 퇴치를 신속히 해결하고 집으로 돌아가려고 하는데, 

마법의 숲에서 재우를 추적하고 있던 불의 마법사 무길이와 마주치게 되었다. 

무길이는 재우를 잡기 위해서 화염 마법을 시전하였고 어느덧 숲은 화염으로 가득차고 있었다. 

재우는 무길이가 화염을 풀어 놓은 숲에서 신속히 요새로 귀환하고자 한다!

 

숲의 지도는 R행과 C열로 이루어져있다. 

비어있는 칸은 '.'로 표시되고, 불은 '*'로, 바위는 'X'로 표시되어있다. 

용사의 집은 'D'로 표현되고, 재우가 처음에 서있는 위치는 'S'로 표시된다.

 

매 분마다 재우는 인접한 4개의 칸(상, 하, 좌, 우)으로 이동할 수 있다. 

불은 매 분마다 인접한 4개의 칸에 불을 옮긴다.

재우는 불과 바위를 지나지 못한다. 

불은 바위와 요새에 옮겨지지 않는다.

 

재우가 탈출을 할 수 있을 때 몇 분 만에 탈출 할 수 있는지 알아보는 프로그램을 작성하라.

 

입력

입력의 첫번째 줄에는 50이하의 정수인 R과 C가 입력된다.

다음 줄부터 지도가 입력되며, 이는 R개의 줄로 이루어져있다. 

각 R개의 줄에는 C개의 문자가 입력된다. 

지도에는 정확히 하나의 용사의 집과 하나의 시작 위치가 입력된다.

 

출력

재우가 숲에서 용사의 집으로 돌아올 수 있을 때 최단 시간(분)을 출력하고,

만약 탈출이 불가능할 경우 "impossible"을 출력한다.

---

접근

불이 퍼지는 시간을 구하여 fire_map이라는 2차원 리스트에 저장한다.

이후 S를 시작으로 BFS를 진행하며 dist라는 2차원 리스트에 시작 위치에서 다른 위치까지 이동할 때 걸리는 시간을 저장한다.

이제 dist와 fire_map에서 같은 위치를 비교하여 dist가 더 작을 때에만 이동할 수 있다고 한다. 만약 dist가 fire_map보다 크거나 같다는 것은 해당 위치로 불길이 오거나 불길이 있다는 뜻이기 때문에 이동할 수 없다.

 

이를 활용하여 D까지 걸리는 시간을 구한다.

 

구현

- 입력받은 맵에서 시작위치를 찾아 sy, sx에 저장하고 해당 위치를 "."(빈칸)으로 표시한다.

- 또한 불의 위치를 찾아 fire_pos에 저장하고 해당 위치를 "."(빈칸)으로 표시한다.

for y in range(N):
    for x in range(M):
        if board[y][x] == 'S':
            sy = y
            sx = x
            board[y][x] = '.'
        if board[y][x] == '*':
            fire_pos.append((y, x))
            board[y][x] = '.'

- 그 다음 불길을 퍼트린다.

- 불길의 시작위치에서 다음 위치까지 도달하는 시간을 BFS를 통해 구한다.

def spread_fire():
    global fire_pos, fire_map
    fire_pos = deque(fire_pos)
    for y, x in fire_pos:
        fire_map[y][x] = 1

    while fire_pos:
        cy, cx = fire_pos.popleft()

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and board[ny][nx] == '.':
                if fire_map[ny][nx] == 0:
                    fire_map[ny][nx] = fire_map[cy][cx] + 1
                    fire_pos.append((ny, nx))

- 이제 S가 이동하여 D에 도달할 수 있도록 BFS로 구해본다.

- 현재 위치에서 dist와 fire_map을 비교하여 dist가 크거나 같고 fire_map이 0이 아닐 때 continue한다.

- 이어서 현재 위치가 D라면 도착한 것이기 때문에 dist의 현재위치에서 -1한 것을 반환한다.

- 큐가 비어서 반복문이 종료되었다면 도착하지 못한 것이기 때문에 -1을 반환한다.

def bfs(y, x):
    global fire_map
    q = deque()
    dist = [[0 for _ in range(M)] for _ in range(N)]
    q.append((y, x))
    dist[y][x] = 1

    while q:
        cy, cx = q.popleft()

        if board[cy][cx] == 'D':
            return dist[cy][cx] - 1
        if dist[cy][cx] >= fire_map[cy][cx] and fire_map[cy][cx] != 0:
            continue

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and board[ny][nx] != 'X':
                if dist[ny][nx] == 0:
                    dist[ny][nx] = dist[cy][cx] + 1
                    q.append((ny, nx))

---

전체 코드

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

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < M)

def spread_fire():
    global fire_pos, fire_map
    fire_pos = deque(fire_pos)
    for y, x in fire_pos:
        fire_map[y][x] = 1

    while fire_pos:
        cy, cx = fire_pos.popleft()

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and board[ny][nx] == '.':
                if fire_map[ny][nx] == 0:
                    fire_map[ny][nx] = fire_map[cy][cx] + 1
                    fire_pos.append((ny, nx))

def bfs(y, x):
    global fire_map
    q = deque()
    dist = [[0 for _ in range(M)] for _ in range(N)]
    q.append((y, x))
    dist[y][x] = 1

    while q:
        cy, cx = q.popleft()

        if board[cy][cx] == 'D':
            return dist[cy][cx] - 1
        if dist[cy][cx] >= fire_map[cy][cx] and fire_map[cy][cx] != 0:
            continue

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and board[ny][nx] != 'X':
                if dist[ny][nx] == 0:
                    dist[ny][nx] = dist[cy][cx] + 1
                    q.append((ny, nx))
    return -1
N, M = map(int, input().split())
board = [list(map(str, input().strip())) for _ in range(N)]
fire_map = [[0 for _ in range(M)] for _ in range(N)]
fire_pos = []
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
for y in range(N):
    for x in range(M):
        if board[y][x] == 'S':
            sy = y
            sx = x
            board[y][x] = '.'
        if board[y][x] == '*':
            fire_pos.append((y, x))
            board[y][x] = '.'

spread_fire()

answer = bfs(sy, sx)
if answer > 0:
    print(answer)
else:
    print('KAKTUS')