[백준 python 5427] 불

[Gold IV] 불 - 5427

문제 링크

성능 요약

메모리: 115624 KB, 시간: 2784 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 2월 2일 20:25:59

문제 설명

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

from collections import deque

t = int(input())
for _ in range(t):
    w, h = map(int, input().split())
    graph = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    fire = deque()
    sang = deque()
    f_time = [[0]*w for _ in range(h)]
    s_time = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if graph[i][j] == "*":
                fire.append([i, j])
                f_time[i][j] = 1
            elif graph[i][j] == "@":
                sang.append([i, j])
                s_time[i][j] = 1

    def f_bfs():
        while fire:
            x, y = fire.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w:
                    continue
                if graph[nx][ny] == "#" or f_time[nx][ny]:
                    continue

                f_time[nx][ny] = f_time[x][y] + 1
                fire.append([nx, ny])

    def s_bfs():
        while sang:
            x, y = sang.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w:
                    return s_time[x][y]
                if graph[nx][ny] == "#" or s_time[nx][ny]:
                    continue
                if not f_time[nx][ny] or f_time[nx][ny] > s_time[x][y] + 1:
                    s_time[nx][ny] = s_time[x][y] + 1
                    sang.append([nx, ny])
        return "IMPOSSIBLE"


    f_bfs()
    print(s_bfs())

 

이 문제는 전에 풀어봤던 문제와 유사하다.

알고리즘은 거의 같고 테스트 개수만큼 출력시켜주면 된다.