[백준 2024/09/23] 3055번 탈출

1. 문제

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

2. 접근 방법

2개의 BFS를 이용해서 문제를 해결할 수 있었다.

 

처음에 지도에 대한 상태를 input으로 받아들이면서, 

'S'와 '*'에 대한 정보를 받아들였다. water에 대한 deque를 만든 후, 물이 퍼져나감에 따라 '.'을 '*'로 고쳐주었다. 물론 범위 안에 있는 지 유무를 확인하였다.

 

고슴도치의 위치 또한 hedge라는 deque에 넣어준 후, 시간이 지남에 따라 위, 아래, 왼쪽, 위로 이동시켜주었다. 이 또한 범위 안에 있는지, 그리고 이동하고자 하는 곳이 '.' 인지 확인하여 주었다.

 

탈출 조건으로는, 만약 hedge의 length가 0일 경우엔, 이동할 수 있는 곳이 없는 것이므로 'KAKTUS'를 반환시켜 주었다.

hedge가 비어지기 전에 beaver의 위치에 도착하게 된다면 year를 반환해 주었다.

 

이렇게만 구성을 해도 test case는 통과하지만, 실제 제출에서 메모리 초과가 발생하였다.

따라서 이를 해결하기 위해 visited list를 만들어서, 고슴도치가 해당 위치에 방문했는지 여부를 확인하였다.

            if (bi, bj) in visited:
                continue
            visited.append((bi, bj))

 

이렇게 구성을 하고 나니, 문제를 맞힐 수 있었다.

 

3. 코드

from collections import deque

def get_hour():
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    year = 0
    visited = []
    while True:
        year += 1
        w_length = len(water)

        for w in range(w_length):
            i, j = water.popleft()
            for l, d in directions:
                if 0 <= i+l < r and 0 <= j+d < c and c_map[i+l][j+d] == '.':
                    c_map[i+l][j+d] = '*'
                    water.append((i+l, j+d))

        b_length = len(hedge)
        if b_length == 0:
            return "KAKTUS"

        for b in range(b_length):
            bi, bj = hedge.popleft()
            if (bi, bj) in visited:
                continue
            visited.append((bi, bj))
            for l, d in directions:
                if 0 <= bi + l < r and 0 <= bj + d < c:
                    if (bi + l, bj + d) == beaver:
                        return year
                    if c_map[bi+l][bj+d] == '.':
                        hedge.append((bi+l, bj+d))


if __name__ == "__main__":
    r, c = map(int, input().split())
    c_map = []
    stone = deque()
    water = deque()
    hedge = deque()
    for i in range(r):
        m = list(input())
        c_map.append(m)
        for j in range(c):
            if m[j] == 'X':
                stone.append((i, j))

            elif m[j] == 'S':
                m[j] = '.'
                hedge.append((i, j))

            elif m[j] == 'D':
                beaver = (i, j)

            elif m[j] == '*':
                water.append((i, j))

    print(get_hour())