DFS/BFS 정복기6 -큐의 길이만큼만 순회해야한다면..-

1. 문제

 

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

3055번: 탈출

 

S에 존재하는 고슴도치가 탈출지점 D로 이동해야하는데, 지도상에 물이 있고, 이 물도 1초에 1번씩 상하좌우로 퍼져나간다.

 

여기서 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다

 

가장 빠른 시간에 탈출할려면 얼마나 걸리는지 구하세요.

 

 

2. 나의 풀이

 

풀이는 전형적인 BFS로 시작점, 도착점을 찾고

 

물도 퍼져나가기 때문에 물이 어디에 있는지도 큐에 담아놔야겠다

 

r,c = map(int,stdin.readline().split())

maps = [list(stdin.readline()) for _ in range(r)]

water_list = deque([])

for y in range(r):
    
    for x in range(c):
        
        if maps[y][x] == 'S':
            
            s_x = x
            s_y = y
        
        elif maps[y][x] == 'D':
            
            g_x = x
            g_y = y
        
        elif maps[y][x] == '*':
            
            water_list.append((x,y))

 

고슴도치랑 탈출점은 하나밖에 없지만 물은 여러군데 있을 수 있으니까 물은 큐에 담아두도록하고

 

다음으로 BFS함수를 구성하면 되는데

 

여기서 중요한 점은 물과 고슴도치가 매초마다 동시에 이동해야한다는 점인데

 

그래서 물부터 전부 탐색하고, 고슴도치 탐색하면 당연히 안됨

 

그리고 고슴도치는 물이 이동할 예정인 칸에는 이동할수가 없어

 

그렇기 때문에 물을 먼저 이동시키고, 다음에 고슴도치를 이동시키면 되겠다

 

그러면 초마다 이동시키는 방법은 어떻게 할까??

 

물이 담겨있는 큐랑, 고슴도치가 담겨있는 큐의 길이를 먼저 구하고,

 

그 길이만큼 탐색 반복문을 순회하면 새로 탐색할 지점은 해당 초에 탐색하지 않고 다음 반복문에 탐색하게 된다

 

def bfs(s_x,s_y,g_x,g_y,r,c,maps,water_list):
    
    visited = [[0]*c for _ in range(r)]

    queue = deque([(s_x,s_y)])

    visited[s_y][s_x] = 1

    while queue:

        len_w = len(water_list)

        for _ in range(len_w):

            w_x,w_y = water_list.popleft()

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                d_w_x = w_x+ni
                d_w_y = w_y+nj

                if d_w_x >= 0 and d_w_x <= c-1 and d_w_y >= 0 and d_w_y <= r-1 and (maps[d_w_y][d_w_x] == '.' or maps[d_w_y][d_w_x] == 'S'):

                    maps[d_w_y][d_w_x] = '*'

                    water_list.append((d_w_x,d_w_y))

 

 

위와 같이 물이 담겨있는 리스트의 길이 len_w를 구한 다음에, 그 len_w만큼 for문을 돌 것이고

 

이 안에서 큐에서 좌표를 빼면서 상하좌우 탐색을 수행한다

 

범위를 벗어나지 말아야하고, 물같은 경우는 X지점이랑 D지점빼고는 다 이동할 수 있기때문에.. 그러한 조건 걸고

 

물을 이동시키면 고슴도치가 이동못하도록 maps의 값을 바꿔주며, 큐에 넣어준다

 

이때 들어가는 새로운 좌표는 len_w로 제약을 걸었기 때문에 현재 반복문에서는 탐색하지 못한다

 

        len_s = len(queue)

        for _ in range(len_s):

            x,y = queue.popleft()

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1 and maps[dy][dx] != '*' and maps[dy][dx] != 'X' and visited[dy][dx] == 0:
                    
                    queue.append((dx,dy))

                    visited[dy][dx] = visited[y][x] + 1

                    if dx == g_x and dy == g_y:
                        
                        return visited[dy][dx]-1
    
    return 'KAKTUS'

 

다음 고슴도치 이동도 큐의 길이를 구해서 len_s만큼 for문 제약을 걸어서

 

새로 탐색해야할 좌표는 다음 반복문에 탐색하도록 만들자

 

당연히 배열을 벗어나면 안되고 고슴도치는 물에는 이동 못하고, X도 이동못하며, visited 배열이 0인 지점만 이동가능하지

 

최소시간을 구하기 위해서 visited[dy][dx] = visited[y][x] + 1 기술 이용했고

 

그리고 탐색하다가 목표지점에 도달했다면, visited[dy][dx] - 1을 return하면 그것이 최소시간일테고

 

이 return문에 도달하지 못하고 while 문이 끝나면 도달을 못한다는 뜻이니까. KAKTUS

 

 

from collections import deque
from sys import stdin

def bfs(s_x,s_y,g_x,g_y,r,c,maps,water_list):
    
    visited = [[0]*c for _ in range(r)]

    queue = deque([(s_x,s_y)])

    visited[s_y][s_x] = 1

    while queue:

        len_w = len(water_list)

        for _ in range(len_w):

            w_x,w_y = water_list.popleft()

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                d_w_x = w_x+ni
                d_w_y = w_y+nj

                if d_w_x >= 0 and d_w_x <= c-1 and d_w_y >= 0 and d_w_y <= r-1 and (maps[d_w_y][d_w_x] == '.' or maps[d_w_y][d_w_x] == 'S'):

                    maps[d_w_y][d_w_x] = '*'

                    water_list.append((d_w_x,d_w_y))
        
        len_s = len(queue)

        for _ in range(len_s):

            x,y = queue.popleft()

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1 and maps[dy][dx] != '*' and maps[dy][dx] != 'X' and visited[dy][dx] == 0:
                    
                    queue.append((dx,dy))

                    visited[dy][dx] = visited[y][x] + 1

                    if dx == g_x and dy == g_y:
                        
                        return visited[dy][dx]-1
    
    return 'KAKTUS'
        


r,c = map(int,stdin.readline().split())

maps = [list(stdin.readline()) for _ in range(r)]

water_list = deque([])

for y in range(r):
    
    for x in range(c):
        
        if maps[y][x] == 'S':
            
            s_x = x
            s_y = y
        
        elif maps[y][x] == 'D':
            
            g_x = x
            g_y = y
        
        elif maps[y][x] == '*':
            
            water_list.append((x,y))

print(bfs(s_x,s_y,g_x,g_y,r,c,maps,water_list))

 

 

3. 되돌아보기

 

매초 탐색을 수행하고 새로 탐색해야할 좌표는 다음 반복문으로 넘기고 싶을때

 

큐의 길이 구하고 - 큐의 길이만큼 for문 - 이 안에서 bfs/dfs 탐색 수행

 

while queue:

 

len_q = len(queue)

 

for _ in range(len_q):

 

x,y = queue.popleft()

 

~~~