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')

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

우선 한 단계씩 퍼져나가야 하기 때문에 BFS를 사용했다.

우선 익은 토마토들의 위치를 가져와야 하기 때문에 반복문을 사용하여 1인 토마토의 위치를 가져온다.

여기서 처음에는 리스트를 사용했었는 데, 시간 초과가 발생한다.

deque를 사용하는 것을 추천한다.

익은 토마토들을 저장할 때 ripe이라는 deque를 사용했는 데, 여기에는 익은 토마토의 위치 뿐만 아니라 지난 날짜까지 저장을 해준다.

이렇게 현재 날짜를 저장해주어야 다음 차례에 날짜를 +1해가며 BFS를 진행할 수 있기 때문이다.

익은 토마토로 부터 4방향을 탐색하고 안 익은 토마토가 있다면, 해당 토마토에 날짜 +1 한 정보와 위치를 ripe deque에 추가해준다.

그리고는 ripe가 남아 있을 동안 반복문을 진행하고 만약 while로 모든 ripe를 탐색한 후에도 0인 토마토가 남아있다면 -1을 출력하며, 아니라면 가지고 있던 max_result를 출력해준다.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

ripe = deque()

for m in range(M):
    for n in range(N):
        if tomato[m][n] == 1:
            ripe.append([0, m, n])

max_result = 0

while ripe:

    cur_cnt, cur_m, cur_n = ripe.popleft()

    max_result = max(max_result, cur_cnt)

    for next_m, next_n in [[cur_m, cur_n + 1], [cur_m, cur_n - 1], [cur_m + 1, cur_n], [cur_m - 1, cur_n]]:
        if 0 <= next_m < M and 0 <= next_n < N and tomato[next_m][next_n] == 0:
            tomato[next_m][next_n] = 1
            ripe.append([cur_cnt + 1, next_m, next_n])


is_finish = True

for m in range(M):
    for n in range(N):
        if tomato[m][n] == 0:
            is_finish = False
            break
    if not is_finish:
        break

print(max_result if is_finish else -1)