[Softeer] 나무 섭지

문제

요약

유령과 남우는 1초에 한칸씩 상하좌우로 이동 가능

남우는 벽 통과 불가능, 유령은 벽 통과 가능

남우가 출구에 도달할 수 있을까?

남우랑 유령이 출구에 동시에 도착하면 통과 못한거임.

 

원본

https://softeer.ai/practice/7726

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

처음에는 dfs나 bfs로 하나씩 다 돌려보려고 했다.

그런데 유령이 중간에 남우를 잡는 다는 것은 출구에서 남우까지의 거리보다

유령들의 출구까지의 거리가 더 가깝다는 게 아닐까? 라는 생각을 하게 되었다.

하나씩 움직일 생각에 아찔했는데 생각보다 싱거웠던 문제,, ㅎㅎ 생각의 전환 필요해..!

 

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
arr = []
now, exit, ghost = (0,0), (0,0), []
visited = [[0] * m for _ in range(n)]
d = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(n):
    arr.append(list(input().strip()))
    for j in range(m):
        if arr[i][j] == 'N':
            now = (i, j)
            visited[i][j] = 1
        elif arr[i][j] == 'D':
            exit = (i, j)
        elif arr[i][j] == 'G':
            ghost.append((i, j))            
        elif arr[i][j] == '#':
            visited[i][j] = 1

q = deque([now])
cnt = 0

def sol():
    global cnt

    while q:
        x, y = q.popleft()

        if (x, y) == exit:
            cnt = visited[x][y]
            return
            
        for dx, dy in d:
            nx, ny = x+dx, y+dy
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0 and arr[nx][ny] not in ('#', 'G'):
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
            
sol()

answer = 'No'
if cnt:
    for x, y in ghost:
        if cnt-1 >= abs(exit[0] - x) + abs(exit[1] - y):
            answer = 'No'
            break
        else:
            answer = 'Yes'

print(answer)