소프티어

n, m = map(int, input().split())

maze = [list(input()) for _ in range(n)]

def dfs(x, y):

  stack = [(x, y, [])] # 좌표와 경로를 함께 저장

  while stack:

    x, y, path = stack.pop(0)

    if 0 <= x < n and 0 <= y < m and maze[x][y] != "#" and maze[x][y] != "G":

      if maze[x][y] == "D":

        path.append((x,y))

        short_path = path[1:]

        #path.append((x, y))

        return short_path # 최단 경로 반환

      if maze[x][y] != "N":

        maze[x][y] = "#"

      stack.append((x, y + 1, path + [(x, y)])) # 오른쪽 이동

      stack.append((x, y - 1, path + [(x, y)])) # 왼쪽 이동

      stack.append((x + 1, y, path + [(x, y)])) # 아래쪽 이동

      stack.append((x - 1, y, path + [(x, y)])) # 위쪽 이동

  return None

ghost_positions = []

player_position = None

for row in range(n):

  for col in range(m):

    if maze[row][col] == "G":

      ghost_positions.append((row, col))

    elif maze[row][col] == "N":

      player_position = (row, col)

path = dfs(player_position[0], player_position[1])

if path:

  ans = True

  for player_x, player_y in path:

    for i, (ghost_x, ghost_y) in enumerate(ghost_positions):

      # 행열을 좌표계로 변환하면 행이 y좌표 열이 x좌표가 된다.

      #print(f"player_y = {player_x}, player_x = {player_y}")

      #print(f"ghost_y = {ghost_x}, ghost_x = {ghost_y}")      

      if 0 <= ghost_x < n and 0 <= ghost_y < m:

        diff_y = player_x - ghost_x

        diff_x = player_y - ghost_y

        if abs(diff_x) >= abs(diff_y):

          # x 방향으로 이동

          # 플레이어가 오른쪽에 있을 때

          if player_y > ghost_y:

            ghost_positions[i] = (ghost_x, ghost_y + 1)

          # 플레이어가 왼쪽에 있을 때

          if player_y < ghost_y:

            ghost_positions[i] = (ghost_x, ghost_y - 1)

        else:

          # y 방향으로 이동

          # 플레이어가 아래쪽에 있을 때

          if player_x > ghost_x:

            ghost_positions[i] = (ghost_x + 1, ghost_y)

          # 플레이어가 위쪽에 있을 때

          if player_x < ghost_x:

            ghost_positions[i] = (ghost_x - 1, ghost_y)

        if player_y == ghost_positions[i][1] and player_x == ghost_positions[i][0]:

          ans = False

          break

        #print(f"ghost_y = {ghost_positions[i][0]}, ghost_x = {ghost_positions[i][1]}")

  if ans:

    print("Yes")

  else:

    print("No")

else:

  print("No")

<수정 전>

시간 초과는 어느정도 예상했는데 오답은 어디서 나올까요

시간 초과는 path를 따라 진행하면서 유령도 같이 따라 움직이는 코드로 변경하면 안나올 것 같습니다.

오답 제 예상은 경로를 A* 알고리즘처럼 N가 최적 경로를 찾는게 아니라 그냥 경로를 활용해서 아마 오류가 나는거 같은데 방법이 도무지 생각이 안나네요.

제 위 코드(아이디어)는

시작 위치, 도착 위치 제외 N 경로를 구해서 이 경로를 따라 G이 움직일 때 같은 위치가 나오면 No를 출력하도록 하는 코드입니다.

<수정 후>

위 코드는 시간 초과만 해결하면 됩니다.

수정 전 오답은 제가 문제를 꼼꼼하게 안읽은 죄였습니다.