[골드4] 5427번 : 불

🛠 문제

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

👩🏻‍💻 해결 방법

상근이와 불의 위치를 따로 큐에 넣어준 뒤, BFS함수에서 불부터 전염시킨 후 상근이를 이동시켜 답을 구할 수 있다


소스 코드

from collections import deque

t = int(input())

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

def bfs():
  cnt = 0  # 시간
  while q:
    cnt += 1
    while fire and fire[0][2] < cnt:
      x, y, time = fire.popleft()

      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w:
          if m[nx][ny] == "." or m[nx][ny] == "@":
            m[nx][ny] = "*"
            fire.append((nx, ny, time+1))
    
    while q and q[0][2] < cnt:
      x, y, time = q.popleft()

      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w:
          if m[nx][ny] == "." and visit[nx][ny] == 0:
            visit[nx][ny] = 1
            q.append((nx, ny, time+1))
        else:
          return cnt
  
  return "IMPOSSIBLE"

for _ in range(t):
  w, h = map(int, input().split())
  m = []
  q = deque()  # 상근이 위치
  fire = deque()  # 불 위치
  visit = [[0] * w for _ in range(h)]

  for i in range(h):
    m.append(list(input().strip()))
    for j in range(w):
      if m[i][j] == "@":
        visit[i][j] = 1
        q.append((i, j, 0))
      elif m[i][j] == "*":
        fire.append((i, j, 0))
    
  print(bfs())