[BOJ] 5427번 불 - python

문제

5427번: 불

 

---

작성한 풀이

불과 상근이는 각각 독립적인 이동 규칙을 가지기 때문에, 불의 위치를 탐색하는 큐와 상근이의 위치를 탐색하는 큐를 따로 관리해 주었다. 

또한 불의 정보에 따라 상근이의 이동이 제한될 수 있기 때문에, 불의 위치에 해당하는 탐색을 먼저 진행해주었다. 

from collections import deque


def solution(boards, row_col, test_case):
    WALL = '#'
    START = '@'
    FIRE = '*'
    IMPOSSIBLE = 'IMPOSSIBLE'

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for i in range(test_case):
        r, c = row_col[i]
        board = boards[i]
        is_escape = False

        visited_f = [[0] * c for _ in range(r)]
        visited_s = [[0] * c for _ in range(r)]

        # 불과 상근이는 각각 독립적인 이동 규칙을 가짐
        # 불의 위치를 탐색하는 큐와 상근이의 위치를 탐색하는 큐를 따로 관리
        queue_f = deque()
        queue_s = deque()

        for n in range(r):
            for m in range(c):
                if board[n][m] == START:
                    queue_s.append((n, m))
                    visited_s[n][m] = 1
                    continue
                if board[n][m] == FIRE:
                    queue_f.append((n, m))
                    visited_f[n][m] = 1

        while queue_f:
            x, y = queue_f.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if nx < 0 or r <= nx or ny < 0 or c <= ny:  # out of range
                    continue
                if visited_f[nx][ny]:
                    continue
                if board[nx][ny] == WALL:
                    continue
                queue_f.append((nx, ny))
                visited_f[nx][ny] = visited_f[x][y] + 1  # 시간에 대한 정보

        while not is_escape and queue_s:
            x, y = queue_s.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if nx < 0 or r <= nx or ny < 0 or c <= ny:  # out of range 인 경우 탈출 성공
                    is_escape = True
                    print(visited_s[x][y])
                    break
                if visited_s[nx][ny]:
                    continue
                if board[nx][ny] == WALL:
                    continue
                # 다음 위치에 불이 번지는 경우의 수 (불이 방문한 적이 있고, 그 시간이 상근이의 (현재 시간 + 1)과 같거나 시간 보다 더 작으면 갈 수 없음)
                if 0 < visited_f[nx][ny] <= visited_s[x][y] + 1:
                    continue
                queue_s.append((nx, ny))
                visited_s[nx][ny] = visited_s[x][y] + 1  # 시간에 대한 정보

        if not is_escape:
            print(IMPOSSIBLE)


test_case = int(input())
boards = []
row_col_info = []
for i in range(test_case):
    w, h = map(int, input().split())
    row_col_info.append((h, w))
    boards.append([list(map(str, input())) for _ in range(h)])

solution(boards, row_col_info, test_case)