[알고리즘][Python] 백준 3055 탈출 문제 풀이

문제 출처 : www.acmicpc.net/problem/3055

3055번: 탈출

---

문제 해석 : 홍수가 일어나고 있고, 고슴도치는 D를 향해서 물을 피해 가야합니다. 이때의 최소 시간을 구하는 문제입니다. 단 도달할 수 없을 경우 실패 문자를 출력합니다.

 

문제 풀이 : 간단한 BFS 알고리즘 통해서 풀 수 있습니다. 물의 이동과 고슴도치의 이동을 유심히 살펴 순서를 정의해주면서 탐색하면 됩니다.

 

풀이 시간 (기록용) : 30분

 

---

풀이 코드

import heapq

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


def move_water():
    global arr
    target = []

    for i in range(R):
        for j in range(C):
            if arr[i][j] == "*":
                for k in range(4):
                    next_x, next_y = i + dx[k], j + dy[k]
                    if 0 <= next_x < R and 0 <= next_y < C:
                        if arr[next_x][next_y] not in ["X", "D", "*"]:
                            target.append([next_x, next_y])
    for element in target:
        x, y = element
        arr[x][y] = "*"


def find(x, y):
    visited = [[False] * C for _ in range(R)]

    Q = []
    heapq.heappush(Q, [0, x, y])
    visited[x][y] = True
    temp_answer = int(1e9)
    now = 0
    while Q:
        count, now_x, now_y = heapq.heappop(Q)

        if arr[now_x][now_y] == "D":
            temp_answer = min(temp_answer, count)

        if now <= count:
            move_water()
            now += 1

        for i in range(4):
            next_x, next_y = now_x + dx[i], now_y + dy[i]
            if 0 <= next_x < R and 0 <= next_y < C and visited[next_x][next_y] is False:
                if arr[next_x][next_y] in [".", "D"]:
                    heapq.heappush(Q, [count + 1, next_x, next_y])
                    visited[next_x][next_y] = True
    if temp_answer != int(1e9):
        return temp_answer
    else:
        return "KAKTUS"


R, C = map(int, input().split())
arr = [list(input()) for _ in range(R)]
x, y = 0, 0
for i in range(R):
    for j in range(C):
        if arr[i][j] == "S":
            x, y = i, j

print(find(x, y))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.