[파이썬] 백준 알고리즘 No.3055 탈출

나의 코드

from collections import deque

n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
sonic = deque()
water = deque()
count = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == '*':
            water.append((i, j))
            visited[i][j] = True
        elif graph[i][j] == 'S':
            sonic.append((i, j))
            visited[i][j] = True
        elif graph[i][j] == 'X':
            visited[i][j] == True

while sonic:
    for _ in range(len(water)):
        wx, wy = water.popleft()
        for i in range(4):
            nx = wx + dx[i]
            ny = wy + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.':
                    water.append((nx, ny))
                    graph[nx][ny] = '*'
                    visited[nx][ny] = True
    count += 1

    for _ in range(len(sonic)):
        sx, sy = sonic.popleft()
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.' and not visited[nx][ny]:
                    sonic.append((nx, ny))
                    visited[nx][ny] = True
                elif graph[nx][ny] == 'D':
                    print(count)
                    exit()
print("KAKTUS")

 

물이 차오르는 것 + 고슴도치가 이동하는 것을 함께 1사이클로 생각하는 bfs 문제.