[백준][파이썬] 3055번 탈출 -BFS

기본적인 BFS 문제에서 조금의 변형이 들어간 문제다.

처음 활용된 것은 물이라는 장애물도 퍼져나간다는것이다.

물 -> 길 ->물 ->길을 while안에서 활용했다

-항상 특정지점의 주변 모두를 한턴에 체크(FALSE)할때는 for(len(stack))구조로 활용해 주면 된다.

-추가적으로 최단거리를 세기 위해서는 다른 리스트를 하나 더 만들어 수를 파악해주면 된다

 

import sys
import collections
n,m = map(int,input().split())
lit =[]
ans =0
for i in range(n):
    tt = list(sys.stdin.readline())
    lit.append(tt)

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(start,wate):
    global ans
    water = wate
    stack = start
    while stack:
        ans += 1
        howmany = len(water)
        for _ in range(howmany):
            t = water[0][0]
            w = water[0][1]
            water.popleft()
            for i in range(4):
                T = t+dx[i]
                W = w+dy[i]
                if 0 <= T <n and 0<=W<m and visited[T][W] == False and lit[T][W] != "D":
                    visited[T][W] = True
                    water.append([T,W])

        for _ in range(len(stack)):
            x = stack[0][0]
            y = stack[0][1]
            stack.popleft()
            for i in range(4):
                X = x+dx[i]
                Y = y+dy[i]
                if  0<=X<n and 0<= Y<m and visited[X][Y] == False:
                    stack.append([X,Y])
                    visited[X][Y] = True
                    count[X][Y] = ans
                    if lit[X][Y] == "D":
                        return ans
    return 0

visited =[[False for i in range(m)] for j in range(n)]
count = [[0 for i in range(m)] for j in range(n)]

start =collections.deque()
water =collections.deque()
arr = []
for i in range(n):
    for j in range(m):
        if lit[i][j] == "S":
            start.append([i,j])
            visited[i][j] = True
        elif lit[i][j] == "*":
            water.append([i,j])
            visited[i][j] =True
        elif lit[i][j] =="D":
            arr.append([i,j])
        elif lit[i][j] =="X":
            visited[i][j] =True

t = bfs(start,water)
if t == 0:
    print("KAKTUS")
else:
    print(t)