[SWEA] 7793 : 오 나의 여신님 - Python

문제

백준 3055 탈출 문제와 동일
최단 시간 구하기
모든 악마는 매 초마다 상하좌우 인접해 있는 영역들을 부식시키며 확장
시작점, 도착점

N행 M열 지도에서 수연이는 말타고 일접한 칸으로 이동
조건 1. 돌이 있는 위치로 이동 못함(벽이라고 생각)
조건 2. 돌이 있는 곳은 악마 역시 확장 안됨
조건 3. 최소 시간으로 도착점으로 이동. 이동 과정에서 아ㅣㄱ마 영역에 포함되면 안된다.

내 코드

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")


blank = "." # 빈칸 이동 가능
devil = "*" # 악마
wall = "X" # 돌(벽)
des = "D"

dx = [-1,0,1,0]
dy = [0,1,0,-1]

def isInner(x,y):
    if 0<=x<n and 0<=y<m:
        return True
    return False

def step1(): # 악마가 해당 칸에 도착하는 시간
    global devil_dq
    dq = devil_dq
    while dq:
        x,y,t = dq.popleft() # 현재 좌표, 현재 좌표까지의 시간
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if isInner(nx,ny) and g[nx][ny] == blank: # 악마가 이동할 수 있음
                if t + 1 < devils[nx][ny]: # 기존 좌표의 최단 거리보다 작으면 갱신 (다익)
                    devils[nx][ny] = t + 1 # 갱신
                    dq.append((nx,ny,t+1))

def step2(a,b): # 이제 저장된 , 악마가 도착하는 시간을 가지고 있는 보드를 바탕으로 가능한지 판단
    global dis
    dq = deque()
    dq.append((a,b,0)) # 현재 수연이의 경로의 시간

    while dq:
        x,y,t = dq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if isInner(nx,ny) and g[nx][ny] == blank: # 일단 이동 가능
                if t + 1 < devils[nx][ny]: # 해당 좌표보다 작은 경우에만 이동 가능
                    if t + 1 < dis[nx][ny]: # 또한 기존 시간보다 작아야만 갱신 가능
                        dis[nx][ny] = t + 1 # 해당 경로로는 t+1초에 이동 가능 (악마X)
                        dq.append((nx,ny,t+1))
            elif isInner(nx,ny) and g[nx][ny] == des: # 도착점이라면
                if t + 1 < dis[nx][ny]: # 갱신이 가능하면 갱신만 하고 끝
                    dis[nx][ny] = t + 1


def printBoard(g):
    print("현재 보드 출력")
    for i in range(n):
        for j in range(m):
            print(g[i][j],end=" ")
        print()


T = int(input())
for t in range(1,T+1):
    n, m = map(int, input().split())  # n행 m열
    g = [list(map(str,input())) for _ in range(n)]

    startX,startY = 0,0
    endX,endY = 0,0

    INF = int(1e9)
    devils = [[INF] * m for _ in range(n)]
    dis = [[INF] * m for _ in range(n)]

    devil_dq = deque()
    for i in range(n):
        for j in range(m):
            if g[i][j] == "*":
                devil_dq.append((i,j,0)) # 악마의 위치 + 해당 좌표의 시간
            if g[i][j] == "S":
                startX,startY = i,j
                g[i][j] = blank
            if g[i][j] == "D":
                endX,endY = i,j # 도착점
    # printBoard(g)
    step1()
    # printBoard(devils)
    step2(startX,startY)
    # printBoard(dis)

    if dis[endX][endY] == INF:
        print(f"#{t} GAME OVER")
    else:
        print(f"#{t} {dis[endX][endY]}")

코멘트

해당 문제는 기본 최단 시간 찾는 문제에 악마가 퍼진다는 조건이 추가된 문제
악마가 확장되는 시간을 미리 devils라는 좌표에 기록
그 이후에 수연이가 특정 좌표에 도착한 시간이 devils에 기록된 시간보다 작아야 함(조건 만족)
거기에 더해서 좌표에 저장된 기존의 최단 시간보다 작은 경우에 갱신 + 해당 좌표에서 다시 탐색(다익스트라)

이 문제는 미리 악마가 특정 좌표에 도달하는 시간을 기록해놓고 수연이를 움직인다고 생각했으면 쉽게 풀 수 있었음.

t + 1 < devils[nx][ny] 이 조건이 바로 해당 좌표에 악마가 도착하는 시간보다 현재경로의 수연이가 해당 좌표에 도착하는 시간이 작은 경우! 이 경우에는 수연이가 해당 좌표에 이동할 수 있다.
t + 1 < dis[nx][ny] 이 조건은 기존에 저장된 최단시간보다 작은 경우에 수연이를 이동시키겠다는 뜻

도착점은 ! 따로 관리 ! 도착점이 갱신되면 해당 좌표에서 큐에 넣으면 안되니깐.