[ BOJ / 파이썬 ] 2574 불

/  23분 경과 시점 첫 풀이   /  ( + No제출 + 기록용 )

import sys

input = sys.stdin.readline
from collections import deque


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

tc = int(input())

for _ in range(tc):
  q = deque([])
  fire = deque([])
  w, h = map(int, input().split())
  board = []
  for i in range(h):
    line = list(input())
    for j in range(w):
      if line[j] == '@':
        line[j] = 0
        q.append((i, j))
      if line[j] == '*':
        fire.append((i, j))
      if line[j] == '.':
        line[j] = 0
    board.append(line)

  cnt = 0
  lose = False
  win = False
  while q:
    cnt = 0
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or h <= nx or ny < 0 or w <= ny:
        win = True
        print(board[x][y] + 1)
        break
      if board[nx][ny] != '#' and board[nx][ny] != '*':
        board[nx][ny] = board[x][y] + 1
    board[x][y] = '.'

    if win:
      print('win')
      break
      
    newfire = deque([])
    while fire:
      fireX, fireY = fire.popleft()
      for i in range(4):
        nfx = fireX + dx[i]
        nfy = fireY + dy[i]

        if 0 <= nfx < h and 0 <= nfy < w and board[nfx][nfy] != '#':
          if board[nfx][nfy] == '.':
            board[nfx][nfy] = '*'
            newfire.append((nfx, nfy))
          else:
            lose = True
            print('INPOSSIBLE')
            break
      if lose:
        break
        
    if win or lose:
      break
    else:
      fire = newfire

테케는 5개인데 답이 3개 나오는 아주 이상한.. 상황, 잘 탈출한 경우가 안 된다.

지금 감이 안 잡히는 것:

1. 두 개가 겹치는 상황에서 어떻게 해야하는가. 두 시점을 상근 이동 q따로, fireQueue따로 돌리는 것이 맞는것인가?

  가장 상위의 while문을 1초라고 가정해서 푼 것인데 맞는것인가.

 

음.. 아이디어 못 떠올리겠어서 역시나 후퇴.. 하, 속상하다.

 

https://velog.io/@ckstn0778/%EB%B0%B1%EC%A4%80-5427%EB%B2%88-%EB%B6%88-O-1-Python

백준 5427번 - 불(★★★ / O / 1) : Python

: 되게 친절하게 풀이하셨고, 문제도 잘 푸셨다. 즌쯔부르으..

 

https://pacific-ocean.tistory.com/391

[백준] 5427번(python 파이썬)

 

 

/  제출  2  /

import sys

input = sys.stdin.readline
from collections import deque


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


tc = int(input())
for _ in range(tc):
  escape = False
  q = deque([])
  w, h = map(int, input().split())
  board = []
  visited = [[-1] * w for _ in range(h)]
  for i in range(h):
    line = list(input())
    for j in range(w):
      if line[j] == '@':
        visited[i][j] = 0
        start = (i, j)
      if line[j] == '*':
        visited[i][j] = 'FIRE'
        q.append((i, j))
    board.append(line)
  q.append(start)

  while q:
    x, y = q.popleft()
    if visited[x][y] == 'FIRE':
      flag = 'FIRE'
    else:
      flag = visited[x][y]

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

      if 0 <= nx < h and 0 <= ny < w:
        if visited[nx][ny] == -1 and (board[nx][ny] == '@' or board[nx][ny] == '.'):
          if flag == 'FIRE':
            visited[nx][ny] = flag
          else:
            visited[nx][ny] = flag + 1
            
          q.append((nx, ny))

      else:
        if flag != 'FIRE':
          print(flag + 1)
          escape = True
          break
          
    if escape:
      break
  if not escape:
    print("IMPOSSIBLE")