100년 뒤 개발자 한승규입니다.

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

구현 과정이 굉장히 어려웠던 문제이다.

우선 처음에 정보를 입력받고 바로 반복문으로 현재 비버의 위치, 목적지, 물의 위치를 각각 배열과 변수에 저장하였다.

그 후에는 당연히 BFS를 진행하였다.

한 턴이 반복 될 때마다 우선 물을 이동시킨다.

. 인 영역이면 물을 전파시켰고, 만약 전파가 되었다면 임시로 만든 deque에 저장하였으며 다음 턴에도 물의 전파를 위해 해당 턴이 끝나면 water deque에 임시 deque를 대입해주었다.

물의 전파가 끝나면 해당 턴에서 다시 비버를 이동시켜야 한다.

당연히 중복을 제거하기 위해 visited 배열을 사용했다.

deque에서 가능한 현재 비버의 위치를 가져왔으며, 만약 해당 위치가 목적지라면 반복문을 탈출 할 수 있도록 하였다.

비버의 위치를 가져온 후에는 4번의 반복을 통해 4 방향으로 이동시켜본 후 만약 해당 위치가 .이거나 목적지라면 visited = True로 바꾸어주고 다음 비버가 이동하기 위해 만든 next_move deque에 넣어준다.

이렇게 move에 데이터가 남아있을 동안 반복하고 모두 반복을 해도 도착하지 못하면 KAKTUS를 출력, 도착 했다면 결과를 출력하면 된다.

import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

result = 0

move = deque()
water = deque()

target_r, target_c = -1, -1

arrive = False

forest = [list(sys.stdin.readline().strip()) for _ in range(R)]

for r in range(R):
    for c in range(C):
        if forest[r][c] == 'S':
            move.append([r, c])
            forest[r][c] = '.'
        elif forest[r][c] == 'D':
            target_r, target_c = r, c
        elif forest[r][c] == '*':
            water.append([r, c])


while move:

    # 물 먼저 이동
    next_water = deque()

    while water:

        cur_r, cur_c = water.popleft()

        for next_r, next_c in [[cur_r, cur_c - 1], [cur_r, cur_c + 1], [cur_r - 1, cur_c], [cur_r + 1, cur_c]]:
            if 0 <= next_r < R and 0 <= next_c < C and forest[next_r][next_c] == '.':
                forest[next_r][next_c] = '*'
                next_water.append([next_r, next_c])

    water = next_water

    # 비버 이동 가능 한 곳으로 이동

    next_move = deque()

    visited = [[False for _ in range(C)] for _ in range(R)]

    while move:

        cur_r, cur_c = move.popleft()

        if cur_r == target_r and cur_c == target_c:
            arrive = True
            break

        for next_r, next_c in [[cur_r, cur_c - 1], [cur_r, cur_c + 1], [cur_r - 1, cur_c], [cur_r + 1, cur_c]]:
            if 0 <= next_r < R and 0 <= next_c < C and (forest[next_r][next_c] == '.' or forest[next_r][next_c] == 'D') and visited[next_r][next_c] is False:
                next_move.append([next_r, next_c])
                visited[next_r][next_c] = True

    move = next_move

    if arrive:
        break

    result += 1

print(result if arrive else 'KAKTUS')