소프티어

아래처럼 코드를 작성했는데, TC는 다 맞는데 제출하니 득점이 0이네요.

혹시 어느 부분이 잘못되었는지 아시는 분 계실까요?

from collections import deque

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

board = [["."] * M for _ in range(N)]

ghosts = []

for i in range(N):

  temp = input()

  for j in range(M):

    if temp[j] == "D":

      DY, DX = i, j

    elif temp[j] == "N":

      NY, NX = i, j

    elif temp[j] == "G":

      ghosts.append((i, j))

    elif temp[j] == "#":

      board[i][j] = "#"

    else:

      continue

def bfs(sy, sx, ey, ex, idx): # idx = 0이면 남우, 1이면 유령

  global board

  visited = [[0] * M for _ in range(N)]

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

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

  dq = deque([(0, sy, sx)])

  visited[sy][sx] = 1

  while dq:

    cnt, y, x = dq.popleft()

    if y == ey and x == ex:

      return cnt

    for i in range(4):

      ny, nx = y + dy[i], x + dx[i]

      if 0 <= ny < N and 0 <= nx < M and not visited[ny][nx]:

        if idx == 0 and board[ny][nx] == "#": continue # 남우는 벽 통과 못함

        dq.append((cnt + 1, ny, nx))

        visited[ny][nx] = 1

  return -1

NW = bfs(NY, NX, DY, DX, 0)

answer = "No" if NW == -1 else "Yes"

for GY, GX in ghosts:

  if bfs(GY, GX, DY, DX, 1) <= NW:

    answer = "No"

    break

print(answer)