백준 3055 - 탈출 Python

ㄱfrom collections import deque
dx, dy = [1,-1,0,0],[0,0,1,-1]
def bfs(arr, R, C, St, Dst, Water):
    cnt = 0
    while St:
        cnt += 1

        # Water move
        for l in range(len(Water)):
            i_, j_ = Water.popleft()
            for k in range(4):
                i = i_ + dx[k]
                j = j_ + dy[k]
                if 0<=i<R and 0<=j<C:
                    if arr[i][j] == '.' or arr[i][j] == 'S':
                        arr[i][j] = '*'
                        Water.append([i,j])

        # Hedgehog move
        for l in range(len(St)):
            i_, j_ = St.popleft()
            for k in range(4):
                i = i_ + dx[k]
                j = j_ + dy[k]
                if i == Dst[0][0] and j == Dst[0][1]:
                    return cnt
                if 0<=i<R and 0<=j<C:
                    if arr[i][j] == '.':
                        arr[i][j] = 'S'
                        St.append([i,j])
    return "KAKTUS"


R, C = map(int,input().split())
arr = [[0] * C for _ in range(R)]
St = deque()
Water = deque()
Dst = deque()

for i in range(R):
    line = input()
    for j in range(C):
        arr[i][j] = line[j]
        if arr[i][j] == 'D':
            Dst.append([i,j])
        elif arr[i][j] == 'S':
            St.append([i,j])
        elif arr[i][j] == '*':
            Water.append([i,j])

print(bfs(arr,R,C, St, Dst, Water))

물에서 한 번, 고슴도치가 한 번 번갈아가면서 bfs를 해주면 됩니다.

 

물이 찰 예정인 칸도 이동할 수 없어서 물에서 먼저 bfs를 합니다!

 

물이 이동할 때 arr[i][j] == 'S'인 경우도 물이 찰 수 있어야 할 것 같은데

 

저 조건이 없어도 동작은 합니다... 반례가 있을 것 같은데 찾아보고 싶네요!