[백준/파이썬] 25307번 시루의 백화점 구경

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

25307번: 시루의 백화점 구경

상당히 까다롭게 풀었던 문제인데, 파이썬 후기가 없어서 글을 남긴다.

우선 시루의 위치에서 시작하여 bfs를 돌리며 매번 마네킹에 근접했는지 검사하는 방식으로 하려 했으나, 당연히 시간초과 및 자잘한 오류들이 많이 생겼다..

 

해결하기 위해선, 마네킹들의 위치에서 bfs를 돌려 마네킹에 근접한 곳들을 따로 체크해둔다. 배열을 이용해도 되고, 벽으로 바꿔버려도 됨!

이제 다시 시루의 위치에서 bfs를 돌리며 갈 수 없는 곳만 잘 검사해주면 문제가 풀릴 것이다!

---

마네킹에서 근접한 곳들을 탐색할 때, while문과 queue의 empty를 이용하지 않고 k만큼만 반복해도 된다.

어차피 거리 k안에만 있어야 하므로 탐색 깊이가 k인 것과 동일하기 때문이다.

import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def manne_bfs():
  while mlist:
    x,y,dist = mlist.popleft()
    if dist == k :
      continue
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]    
      
      if nx >= n or nx < 0 or ny < 0 or ny >= m:
        continue
      if danger[nx][ny]:
        continue
      
      danger[nx][ny] = True
      mlist.append((nx,ny,dist+1))

def bfs(sx,sy,hp): 
  q = deque()
  q.append((sx,sy,hp))
  visited[sx][sy] = True
  
  while q:
    x,y,hp = q.popleft()
    
    if board[x][y] == 2:
      return hp 
  
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      
      if nx >= n or nx < 0 or ny < 0 or ny >= m:
        continue
      if board[nx][ny] == 1 or visited[nx][ny] or danger[nx][ny]:
        continue
      
      visited[nx][ny] = True
      q.append((nx,ny,hp+1))
  return -1

if __name__ == "__main__":
  n,m,k = map(int,input().split())
  
  board = []
  danger = [[False for _ in range(m)] for _ in range(n)]
  visited = [[False for _ in range(m)] for _ in range(n)]
  sx,sy=0,0
  mlist = deque()
  dx = [1,0,-1,0]
  dy = [0,1,0,-1]
  
  for i in range(n):
    info = list(map(int,input().split()))
    board.append(info)
    for j in range(len(info)):
      if info[j] == 4:
        sx = i
        sy = j
      elif info[j] == 3:
        mlist.append([i,j,0])
        board[i][j] = 1
        danger[i][j] = True
  #print(board)
  if k!= 0:
    manne_bfs()

  print(bfs(sx,sy,0))