BFS&DFS 정복기

BFS

 

주로 deque를 사용하며 시작하게 된다.

from collections import deque

 

이후 사용할 배열을 입력 받고

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

 

방문을 확인하는 visited 배열을 만들게 된다.

def BFS(x,y):
    queue=deque()
    queue.append((x,y))
    visited[x][y]=True
    while queue:
        dx=[1,-1,0,0,1,1,-1,-1]
        dy=[0,0,1,-1,1,-1,1,-1]
        x,y=queue.popleft()
        for i in range(8):
            hx=x+dx[i]
            hy=y+dy[i]

            if hx<0 or hy<0 or hx>=M or hy>=N:
                continue
            elif a[hx][hy]==1 and visited[hx][hy]==False:
                a[hx][hy]=0
                visited[hx][hy]=True
                queue.append((hx,hy))

 

보통 dx,dy에서 방향을 설정하게 되는데 문제의 조건마다  4방향,혹은 8방향으로 나뉘게 된다.

 

주변을 확인할 때 범위를 넘어가는지 확인하고 ,elif 구문에 주로  bfs문제의 조건을 채워 넣게 된다.

 

조건에 만족한 좌표는 다시 queue에 넣어 주게 되면서 다음으로 확인할 좌표로 넣게 된다.

 

이때 방문하지 않은 좌표만을 넣어야 하는 것을 주위해야한다.

 

DFS