글 읽기 - 완벽히 짠 거 같은데 어디가 잘못됐을까요 ㅜ 반례 부탁드립니다

jyg0599 3년 전 0

테스트케이스마다 입력받아서 bfs 돕니다

bfs에서 불 한번 지르고 상근이 이동시키는 방식인데 어느 로직이 잘못된 건지 모르겠습니다.

반례 혹은 틀린부분 지적해주시면 감사하겠습니다

from collections import deque
import sys

tc = int(sys.stdin.readline())
dx = [-1,0,1,0]
dy = [0,1,0,-1]

def fire():
  qlen = len(fire_q)
  for _ in range(qlen):
    x, y = fire_q.popleft()
    for dir in range(4):
      nx = x + dx[dir]
      ny = y + dy[dir]
      if (0<=nx<row) and (0<=ny<col):
        if field[nx][ny] == '.':
          field[nx][ny] = '*'
          fire_q.append((nx, ny))

def bfs():
  while dog_q:
    fire()
    qlen = len(dog_q)
    for _ in range(qlen):
      x, y = dog_q.popleft()
      for dir in range(4):
        nx = x + dx[dir]
        ny = y + dy[dir]
        if (0<=nx<row) and (0<=ny<col):
          if field[nx][ny] == '.' and dog_field[nx][ny] == 0:
            dog_field[nx][ny] = dog_field[x][y] + 1
            dog_q.append((nx, ny))
        else:
          print((dog_field[x][y]))
          return
  print("IMPOSSIBLE")

for _ in range(tc):
  col, row = map(int, sys.stdin.readline().split(" "))
  field = [list(map(str, sys.stdin.readline().strip())) for _ in range(row)]
  dog_field = [[0] * col for _ in range(row)]
  dog_q = deque()
  fire_q = deque()
  for i in range(row):
    for j in range(col):
      if field[i][j] == '*': fire_q.append((i,j))
      if field[i][j] == '@': 
        dog_q.append((i,j))
        field[i][j] = '.'
        dog_field[i][j]=1
  bfs()

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

완벽히 짠 거 같은데 어디가 잘못됐을까요 ㅜ 반례 부탁드립니다

jyg0599 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말