[Python] [BOJ] 탈출(3055)

💡 문제 해결

1. 시작점과 도착지점, 물의 좌표를 변수에 저장
2. 고슴도치가 이동할 수 있는 장소가 있는동안 반복문 실행
3. 다음차례에 물이 이동하는 칸은 고슴도치가 이동할 수 없는 칸이기 때문에 물 먼저 이동
4. 저장해둔 물이 존재하는 좌표들을 통해 물을 확산시키고, 1턴 동안 확산된 물의 좌표값들을 갱신
5. 고슴도치가 움직일 수 있는 좌표들을 통해 1턴 동안 이동할 수 있는 좌표값들을 갱신
6. 고슴도치가 도착점에 도착한다면 stack을 비워 반복문을 break
7. 만약 고슴도치가 이동할 수 있는 좌표가 더이상 존재하지 않는다면 처음 설정한 answer을 출력

📌 1턴씩 이동한다는 개념을 생각해내는 것이 관건인 문제

🧾 문제 설명

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 
그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 
이 숲에는 고슴도치가 한 마리 살고 있다. 
고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 
물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 
비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. 
(위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 
물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 
물과 고슴도치는 돌을 통과할 수 없다. 
또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 
고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 
즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 
이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

문제보기

🖨 입출력

📝 풀이

import sys

input = sys.stdin.readline
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def move(answer, stack):
    tmp_stack = []
    for x, y in stack:
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                # arrive end point
                if nx == end[0] and ny == end[1]:
                    answer = arr[x][y] + 1
                    return answer, []
                # if move next point
                if arr[nx][ny] == '.':
                    arr[nx][ny] = arr[x][y] + 1
                    tmp_stack.append((nx, ny))
    return answer, tmp_stack


def move_waters(waters):
    tmp_waters = []
    for water_x, water_y in waters:
        for k in range(4):
            wx = water_x + dx[k]
            wy = water_y + dy[k]
            if 0 <= wx < R and 0 <= wy < C:
                if arr[wx][wy] == '.':
                    arr[wx][wy] = '*'
                    tmp_waters.append((wx, wy))
    return tmp_waters



R, C = map(int, input().split())
arr = [list(map(str, input()))[:C] for _ in range(R)]

waters = []
# set start, end point, water point
for i in range(R):
    for j in range(C):
        if arr[i][j] == 'S':
            start = (i, j)
            arr[i][j] = 0
        elif arr[i][j] == 'D':
            end = (i, j)
        elif arr[i][j] == '*':
            waters.append((i, j))

answer = 'KAKTUS'
stack = [start]
while stack:
    # move waters
    waters = move_waters(waters)

    # move 
    answer, stack = move(answer, stack)

print(answer)

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/3055