소프티어

import sys
from collections import deque


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


grid = [list(sys.stdin.readline().strip()) for _ in range(n)]
ds = [(1, 0), (-1, 0), (0, 1), (0, -1)]


ghost_pos_list = []


for i in range(n):
    for j in range(m):
        if grid[i][j] == 'D':
            dest_pos = [i, j]
        elif grid[i][j] == 'G':
            ghost_pos_list.append([i, j])
        elif grid[i][j] == 'N':
            start_pos = [i, j]




def calc_namwoo_short(grid, start_pos):
    visited = [[False] * m for _ in range(n)]
    queue = deque([[start_pos[0], start_pos[1], 0]])
    while queue:
        x, y, cnt = queue.popleft()
        visited[x][y] = cnt
        if [x, y] == dest_pos:
            break
        for dx, dy in ds:
            if 0<= x+dx < n and 0<= y+dy < m and visited[x+dx][y+dy] == False and grid[x+dx][y+dy] != '#':
                queue.append([x+dx, y+dy, cnt+1])
    return visited[dest_pos[0]][dest_pos[1]]


namwoo_short = calc_namwoo_short(grid, start_pos)


result = 'Yes'
if namwoo_short == False:
    result = 'No'
else:
    for ghost_pos in ghost_pos_list:
        ghost_short = abs(ghost_pos[0] - dest_pos[0]) + abs(ghost_pos[1] - dest_pos[1])
        if ghost_short <= namwoo_short:
            result = 'No'
            break


print(result)

파이썬 시간초과가 뜨는데, 어느부분이 문제일까요..? 도와주시면 감사하겠습니다