[PY] 3055 : 탈출

https://www.acmicpc.net/problem/3055

이 문제에 대한 아이디어에 대해 생각이 많았지만 내가 실시간으로 움직이기엔 구현 난이도가 좀 버거웠다. 따라서
물에 대한 내용을 수행하여 비버 이동에 대한 기본 틀을 마련한 다음, 그 이후에나 비버 이동에 영향을 미치도록 해서 상당히 가독성 있게 해결 해낸 케이스이다.

끝 판에 메모리 초과 이슈로 파일럿 코의 도움을 다소 받았다.

 

 

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

fieldX, fieldY = map(int, input().split())
fieldStatus = [[] for _ in range(fieldX)]
waterStatus = [[-1] * fieldY for _ in range(fieldX)]
playerStatus = [[-1] * fieldY for _ in range(fieldX)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(fieldX):
    inputField = input().strip()
    fieldStatus[i] = list(inputField)

waterStart = []
# 전체 순회를 돌면서 체크한다.
# 물 입장에서
waterQ = deque()
playerQ = deque()
for i in range(fieldX):
    for j in range(fieldY):
        if(fieldStatus[i][j] == '*'):
            waterStatus[i][j] = 0
            waterQ.append((i, j))
        elif(fieldStatus[i][j] == 'S'):
            playerQ.append((i, j))
            playerStatus[i][j] = 0
        elif(fieldStatus[i][j] == 'X'):
            waterStatus[i][j] = float('inf')
            playerStatus[i][j] = float('inf')



while waterQ:
    x, y = waterQ.popleft()
    spreadTime = waterStatus[x][y] + 1
    for i in range(4):
        tmpX = x + dx[i]
        tmpY = y + dy[i]

        if(0 <= tmpX < fieldX and 0 <= tmpY < fieldY):
            if(waterStatus[tmpX][tmpY] == -1 and fieldStatus[tmpX][tmpY] not in ('X', 'D')):
                waterStatus[tmpX][tmpY] = spreadTime
                waterQ.append((tmpX, tmpY))


while playerQ:
    x, y = playerQ.popleft()
    arrival = playerStatus[x][y] + 1
    for i in range(4):
        tmpX = x + dx[i]
        tmpY = y + dy[i]

        if(0 <= tmpX < fieldX and 0 <= tmpY < fieldY):
            if(fieldStatus[tmpX][tmpY] == 'D'):
                print(f"{arrival}")
                exit()

            if playerStatus[tmpX][tmpY] == -1 and (waterStatus[tmpX][tmpY] == -1 or arrival < waterStatus[tmpX][tmpY]):
                playerStatus[tmpX][tmpY] = arrival
                playerQ.append((tmpX, tmpY))

print("KAKTUS")