[백준] 5427번 : 불

5427번: 불

5427번: 불

🤔 문제분석

너비우선탐색을 이해하면 쉽게 풀 수 있는데, 불을 먼저 방문한뒤 승범이를 방문하면 불이 먼저 번지게되고 번지지 않은 위치를 승범이가 탐색 할 수 있으니 문제에서 요구하는 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동 할 수 없는 조건을 잘 만족 시킬 수 있습니다.

💻 코드

import sys
from collections import deque
input = sys.stdin.readline
moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

T = int(input())

for _ in range(T):
    w, h = map(int, input().split())
    graph = []
    queue = deque()
    visited = [[False for _ in range(w)] for _ in range(h)]
    
    sungbum = None, None
    for i in range(h):
        temp = list(input().strip())
        for j in range(w):
            if temp[j] != '.':
                visited[i][j] = True
                if temp[j] == "@":
                    sungbum = i, j
                else:
                    queue.append((i ,j, temp[j], 0))

        graph.append(temp)
    
    queue.append((sungbum[0], sungbum[1], "@", 0))
    is_finished = False
    while queue:
        y, x, c, cost = queue.popleft()
        
        for dy, dx in moves:
            ny, nx = dy + y, dx + x
            if is_finished:
                break
            
            # 불일때
            if c == '*' and h > ny >=0 and w > nx >=0 and not visited[ny][nx] and graph[ny][nx] == '.':
                graph[ny][nx] = c
                visited[ny][nx] = True
                queue.append((ny, nx, c, cost))
            
            # 상은이 일때
            if c == '@':
                if h > ny >=0 and w > nx >=0:
                    if graph[ny][nx] == '.' and not visited[ny][nx]:
                        graph[ny][nx] = c
                        visited[ny][nx] = True
                        queue.append((ny, nx, c, cost + 1))
                else:
                    print(cost + 1)
                    is_finished = True
                    break
    if not is_finished:
        print("IMPOSSIBLE")