소프티어

import sys

from collections import deque

import copy

#### module import ####

q = deque()

ghost = deque()

exit = [] #Exit index

initial_dist = 0

n, m = map(int, sys.stdin.readline().split())

array = []

for i in range(n):

  li = list(input())

  if 'N' in li:

    x, y = i, li.index('N')

    a = []

    a.append((x, y))

    q.append((x, y, a))

  if 'G' in li:

    x, y = i, li.index('G')

    ghost.append((x, y))

  if 'D' in li:

    x, y = i, li.index('D')

    exit.append(x)

    exit.append(y)

  array.append(li)

#### test ####

ghost_short = int(1e9)

initial_dist = abs(q[0][0] - exit[0]) + abs(q[0][1] - exit[1])

while ghost:

  x, y = ghost.popleft()

  ghost_short = min(ghost_short, abs(x - exit[0]) + abs(y - exit[1]))

if ghost_short <= initial_dist:

  print('No')

else:

  #### parameter input ####

  visit = [[0] * m for _ in range(n)]

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

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

  exit_cost = int(1e9)

  #### initial setting ####

  while q:

    x, y, history = q.popleft()

    h = copy.deepcopy(history)

    if visit[x][y] == 1:

      continue

    h.append((x, y))

    if array[x][y] == 'D':

      if len(h) < exit_cost:

        exit_cost = len(h) - 2

        break

    visit[x][y] = 1

    for i in range(4):

      nx = x + dx[i]

      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < m and (array[nx][ny] == '.' or array[nx][ny] == 'D'):

        q.append((nx, ny, copy.deepcopy(h)))

  #### Check Exit ####

  if exit_cost == 0 or exit_cost >= ghost_short:

    print('No')

  else:

    print('Yes')

코드는 위와 같은데

핵심은

유령이 목적지까지 도달하는 최단 거리가 bfs로 탐색한 최소 거리보다 짧거나 같으면 No를 출력하는 건데

bfs 부분에서 시간 절약을 어떻게 해야할지 모르겠네요 ㅠ