BFS 알고리즘 유형별로 기본 틀 정리(기초, 미로찾기, 확산)

1. 가장 기본형태

 

방문배열 visited 생성

 

빈 큐에 방문 시작할 정점 v를 넣고

 

v에 대한 방문처리

 

큐가 빌때까지 반복문 - 큐에서 정점 v를 빼고

 

v에 대해 할일을 수행하면서 

 

v에 인접한 정점 w중에 방문하지 않은 w라면 다시 큐에 넣고 w에 대해 방문처리

def bfs(v,N): #시작정점 v, 마지막 정점 N
    
    #visited 생성

    visited = [0] * (N+1)

    #큐를 생성함

    q = [] 

    q.append(v) #시작점이 들어간 큐
    ### q=[v] 

    visited[v] = 1

    while q: #큐가 비어있지 않다면 탐색
        
        v = q.pop(0) #시작점 뽑아내기

        #방문한 v를 이용해 할일
        print(v)

        #인접하고 미방문한 (in queue되지 않은) 정점 w가 있으면...

        for w in adjList[v]: #v에 인접한 정점 w에 대하여
            
            if visited[w] == 0: #방문한 적이 없는 정점이라면..
                
                q.append(w)
                visited[w] = 1

 

 

2. 조금 더 빠른 기본형태

 

deque를 이용하면 정점이 많아질수록 더 빠르다

 

from collections import deque

def bfs(v,N): #시작정점 v, 마지막 정점 N
    
    #visited 생성

    visited = [0] * (N+1)

    #큐를 생성함

    q = deque()

    q.append(v) #시작점이 들어간 큐
    ### q=deque([v])

    visited[v] = 1

    while q: #큐가 비어있지 않다면 탐색
        
        v = q.popleft() #시작점 뽑아내기

        #방문한 v를 이용해 할일
        print(v)

        #인접하고 미방문한 (in queue되지 않은) 정점 w가 있으면...

        for w in adjList[v]: #v에 인접한 정점 w에 대하여
            
            if visited[w] == 0: #방문한 적이 없는 정점이라면..
                
                q.append(w)
                visited[w] = 1

 

 

3. 방문거리를 구하는 방법

 

visited 배열에 1을 저장하지 않고, 이전 visited값에 1을 더한 값을 저장한다면

 

방문거리가 1씩 증가하게 되는 형태가 된다

 

visited[w] = visited[v] + 1로 저장하는게 중요함

 

def bfs(v,N): #시작정점 v, 마지막 정점 N
    
    #visited 생성

    visited = [0] * (N+1)

    #큐를 생성함

    q = [] 

    q.append(v) #시작점이 들어간 큐
    ### q=[v] 

    visited[v] = 1

    while q: #큐가 비어있지 않다면 탐색
        
        v = q.pop(0) #시작점 뽑아내기

        #방문한 v를 이용해 할일
        print(v)

        #인접하고 미방문한 (in queue되지 않은) 정점 w가 있으면...

        for w in adjList[v]: #v에 인접한 정점 w에 대하여
            
            if visited[w] == 0: #방문한 적이 없는 정점이라면..
                
                q.append(w)
                visited[w] = visited[v] + 1

4. 찾고자하는 목표지점에 대한 탐색

 

큐에서 정점을 빼면서, 방문한 정점이 목표 지점인지 확인하고 목표지점이면 바로 break해서 return하면 된다

 

def bfs(v,N,t): #시작정점 v, 마지막 정점 번호 N, 도착하고자 하는 정점 t
    
    visited = [0] * (N+1)

    q - []

    q.append(v) 

    visited[v] = 1

    while q:
        
        v = q.pop(0)

        ##내가 찾고자하는 목표인지 확인하는게 이 문제의 목적

        if v == t:
            
            return 1 #목표를 찾음
        
        for w in adjList[v]:
            
            if visited[w] == 0:
                
                q.append(w)
                visited[w] = visited[v] + 1

 

5. 상하좌우를 모두 탐색하는 이차원 배열에서의 bfs

 

델타배열 [[0,1],[1,0],[0,-1],[-1,0]]을 이용해서 v에 대한 인접 정점이 4가지임을 이용하면 된다

 

시작점은 (x,y)이고, 이것을 큐에 넣고

 

visited도 이차원 배열(N*N or M*N)로 초기화하며

 

특히 이동하는 좌표 (ni,nj)가 단순히 방문했냐 아니냐 뿐만 아니라

 

이차원 배열의 범위를 벗어났는지, 이동이 불가능한 곳인지도 검사해야한다

 

0 <= ni and 0 <= nj and ni < N and nj < N and maze[ni][nj] != 1 and visited[ni][nj] == 0

 

def bfs(i,j,N):
    
    visited = [[0]*N for _ in range(N)]

    q = []
    q.append((i,j))

    visited[i][j] = 1

    while q:
        
        i,j = q.pop(0)

        #도착지인가 아닌가?

        if maze[i][j] == 3:
            return 1
        
        for di,dj in [[0,1],[1,0],[0,-1],[-1,0]]: #상하좌우 탐색
            
            ni,nj = i+di, j+dj

            if 0 <= ni and 0 <= nj and ni < N and nj < N and maze[ni][nj] != 1 and visited[ni][nj] == 0:
                  
                  q.append((ni,nj))
                  visited[ni][nj] = visited[i][j] + 1 ##이렇게 하면 출발점에서 도착점까지의 최단거리를 알 수 있는?

    return 0

 

6. 시작정점이 여러개인 BFS

 

그냥 여러개의 정점을 첫 큐에 모두 넣고 BFS를 수행하면 된다

 

바이러스 확산하는데 얼마나 걸리는지, 이런 문제로 많이 나온다

 

visited에 +1씩 더하면서 저장했기때문에 가득 차는데 걸리는 시간은 visited를 이용해서 구할 수 있다

 

def bfs(N):
    visited = [[0]*N for _ in range(N)]

    q = []

    ##시작점을 모두 찾아서 탐색 시작

    for i in range(N):
        
        for j in range(N):
            
            if maze[i][j] == 2:
                
                q.append((i,j))
                visited[i][j] = 1
    
    while q:
        
        i,j = q.pop(0)

        for di,dj in [[0,1],[1,0],[-1,0],[0,-1]]:
            
            ni,nj = i+di,j+dj 

            if 0<=ni<N and 0<=nj<N and maze[ni][nj] != 1 and visited[ni][nj] == 0: #벽으로 둘러싸인 미래라서 범위 검사를 안함
                q.append((ni,nj))
                visited[ni][nj] = visited[i][j] + 1

                ###if max_v < visited[i][j]:
                    ###max_v = visited[i][j] ##맥스값 갱신하거나, visited 순회해서 맥스값 찾거나

 

혹은 처음에 queue에서 정점을 빼기 전에, size를 구한다음에 queue의 size만큼 for문을 돌고, 거기에서 queue의 정점을 빼기 시작한다

 

그러면 처음에 q = [a,b] 2개 있으면.. 2개에 대해서 탐색을 시작하는데

 

처음에 size=2를 구하고 2만큼만 반복문을 수행하자.

 

그러면 a에 대해서 반복문을 수행하고 a와 인접했지만 방문해야할 정점 모두 큐의 오른쪽에 넣은 다음에

 

b에 대해 똑같이 수행하고, 2번만 수행했으니까 for _ in range(size)를 나가고,

 

다시 큐의 사이즈를 구해서, 그 사이즈만큼 반복...

 

큐가 모두 빌때까지 계속 반복

 

이것도 뭔가 중요한것 같은데

 

while queue:

     

    size = len(queue)

    

    for _ in range(size):

        v = queue.pop(0)

 

def bfs(i,j,N,visited):
    

    queue = [(i,j)]

    visited[i][j] = 1
    day = 0

    while queue:

        size = len(queue)

        print(f'{day}일차')
        print('############')

        for k in range(n):
            
            print(visited[k])
        
        print('############')

        for _ in range(size):

            i,j = queue.pop(0)

            for di,dj in [[0,1],[1,0],[-1,0],[0,-1]]:
                
                ni = i + di
                nj = j + dj

                if (ni >= 0 and ni <= N-1) and (nj >= 0 and nj <= N-1) and visited[ni][nj] == 0:
                    
                    queue.append((ni,nj))
                    visited[ni][nj] = visited[i][j] + 1
        
        day += 1


N = 10

visited = [[0]*N for _ in range(N)]

print(bfs(5,5,10,visited))