[소프티어]lv3. 나무 섭지 (Python)

1.문제

https://softeer.ai/app/assessment/index.html?xid=132454&xsrfToken=i9dyxMu8sCXqxYFy3CT6AkZMoUoaYcXW&testType=practice

2.풀이

• 완전탐색으로 풀기엔 n, m <= 1000 이므로 시간 초과가 걸린다.
• 풀이 힌트에선 multi-source bfs 라고 하던데, 쉽게 말해 모든 칸에서 직접 다 움직이는게 아니고,
  • 하나의 유령 좌표를 알아놓고, 그 유령이 움직이는(상하좌우) 좌표를 미리 다 표시해두는 것이다.
  • 일반적으로 4개의 방향을 갈때마다 그 위치를 q.append 해주는 방식 + visited를 합쳐놓은 거라고 보면 된다.

[코드 풀이]

• 벽, 탈출구만 써있는 board 배열을 만들고, 나머지(남우, 유령)는 다 좌표로 저장한다
• 먼저 유령 좌표를 모두 받아놓고 -> 유령이 움직인 시간을 표시한 ghost_board를 만들어놓는다.
  • ghost_board: 유령이 움직임을 기록한 배열, 초기값 0
• 유령이 움직인 시간을 써놓는다. -> 유령은 필요에 따라 안움직이고 버틸 수도 있다. -> 그러므로 남우가 (2, 3)으로 움직였을때, 유령이 그 칸에 온 시간이 남우보다 작거나 같으면! 미리 유령이 왔다가 남우를 기다렸을 수도 있으므로
  • 남우 시간 >= 유령 시간 이면 "유령한테 잡혔다"고 간주한다.
• 만약 유령한테 안잡혔으면, 이제 벽인지, 탈출구인지 확인하여 일반적인 BFS 처럼 큐(move)에 넣어준다.
  • 이때도 방문했던 공간에 다시 안가도록, 남우가 간 곳도 시간 숫자로 표시해준다.

import sys
from collections import deque

n, m = map(int, input().split())
board = []
answer = ""

for _ in range(n):
    board.append(list(input()))

ghosts = deque([])
namwoo = (0, 0)
# board에 벽, 출구만 표시
# 나머지는 위치좌표만 갖고 있기
for i in range(n):
    for j in range(m):
        if board[i][j] == "N":
            namwoo = (i, j)
            board[i][j] = "."
        if board[i][j] == "G":
            ghosts.append((i, j))
            board[i][j] = "."

# namwoo가 있는 쪽으로 
# 모든 유령들이 하나같이 퍼지는 걸로해서 작은 수가 있으면 작은 수를 기준으로 퍼지기

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque(ghosts)

# 유령 방문 배열
ghost_board = [[0] * m for _ in range(n)]

while q:
    gx, gy = q.popleft()
    for i in range(4):
        nx, ny = gx + dx[i], gy + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if ghost_board[nx][ny] != 0:
            continue
        ghost_board[nx][ny] = ghost_board[gx][gy] + 1
        q.append((nx, ny))
        if ghost_board[gx][gy] == 0:
            ghost_board[gx][gy] = 1


# 남우가 움직이는데, 움직이는 공간에 그 유령의 시간 수가 <= 면 끝나는 것 (거기 멈출 수도 있기 때문에)
# 남우가 움직일 수 있는 곳
# ghost가 있는지 확인 후 -> 숫자가 크거나 없으면 -> 벽이 있는지 확인 -> 이동 후 그 곳이 exit인지 확인
move = deque([(namwoo[0], namwoo[1], 0)])
while move:
    x, y, time = move.popleft()

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if ghost_board[nx][ny] <= time:
            continue
        if board[nx][ny] == "#":
            continue
        if board[nx][ny] == "D":
            answer = "Yes"
            break
        if board[nx][ny] == ".":
            move.append((nx, ny, time + 1))
            board[nx][ny] = time + 1

if not answer:
    answer = "No"



print(answer)