[Softeer] 나무 섭지

문제링크

---

나무 섭지

풀이과정

---

241101 오늘의 마지막 풀이 문제 ... 끝까지 잡고 늘어졌다 .. 하아 나자신 잘해써 칭찬해 ..

BFS를 이용해서 풀었고, 남우와 귀신들의 시작 점을 기준으로 BFS를 진행했다.

우선 귀신들의 위치에서 각 초에 갈 수 있는 맵의 위치에 해당 시간을 기록해줬다. (이동거리와 동일하다고 볼 수 있다)
무슨말이냐면 0초에 귀신이 (2,1)에 있다면, 1초에는 (2,0), (1,1), (3,1), (2,2)에 위치할 수 있다는 것이다.
그래서 이걸 출력해보면 다음과 같다.

>>> G_time
[[3, 2, 3, 4, 5, 6],
 [2, 1, 2, 3, 4, 5],
 [1, 0, 1, 2, 3, 4],
 [0, 1, 2, 3, 4, 5]]

그리고 나서 남우의 위치에서 목적지까지 가는 시간을 계산한다.
만약 목적지까지 갈 수 없다면 -1을 리턴받고, 목적지에 갈 수 있다면 목적지까지 가는 시간을 리턴받는다.

마지막으로 조건을 걸어서 탈출 유무를 파악하면 된다.

1. 남우가 목적지에 갈 수 있을 때
   → 목적지에 도착했을 때 귀신이 걸린 시간이 남우가 걸린 시간보다 적다면 ? → 남우는 탈출 불가(귀신한테 잡힌다)

2. 남우가 목적지에 갈 수 없을 때
   → 남우는 무조건 탈출 불가

코드

---

import sys
from collections import deque

directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
n, m = map(int, input().split())
maps = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

def bfs(start, is_namwoo):
    q = deque()
    visited = [[-1] * m for _ in range(n)]

    for x, y in start:
        q.append([x, y, 0])
        visited[x][y] = 0

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

        # 남우가 목적지에 도착하면 걸린 시간만 리턴
        if is_namwoo and maps[x][y] == 'D':
            return time

        # 남우 / 귀신이 이동하면 시간 증가해서 방문 기록
        for dx, dy in directions:
            mx, my = x + dx, y + dy
            if 0 <= mx < n and 0 <= my < m and visited[mx][my] == -1:
                if is_namwoo:
                    if maps[mx][my] != '#':
                        q.append([mx, my, time + 1])
                        visited[mx][my] = time + 1
                else:
                    q.append([mx, my, time + 1])
                    visited[mx][my] = time + 1

    return visited if not is_namwoo else -1

N_start = []
G_start = []

for i in range(n):
    for j in range(m):
        if maps[i][j] == 'N':
            N_start.append([i, j])
        elif maps[i][j] == 'G':
            G_start.append([i, j])

G_time = bfs(G_start, False)
N_time = bfs(N_start, True)
# print(G_time,N_time)

if N_time != -1:
    escape = True
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'D' and G_time[i][j] != -1 and G_time[i][j] <= N_time:
                escape = False
                break
        if not escape:
            print('No')
            sys.exit()
    print('Yes')

else:
    print('No')
    

결과

---