[알고리즘] 탐색 알고리즘(DFS, BFS)

*DFS (깊이 우선 정렬)

• 그래프 완전 탐색을 위한 구현
• 재귀함수, 스택 자료구조로 구현가능
• 시간복잡도 = O(V+E) 여기서 V=노트 수, E= 간선 수

#백준 11724 DFS예시 코드
import sys
sys.setrecursionlimit(10000)
input= sys.stdin.readline

def dfs(v):
    visited[v]=True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

N,M = map(int, input().split())
graph=[[] for _ in range(N+1)]
visited=[False]*(N+1)

for _ in range(M):
    u,v= map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

cnt=0

for i in range(1,N+1):
    if not visited[i]:
        cnt+=1
        dfs(i)
print(cnt)

*핵심  이론 

1. 시작할 노드를 정한 후 초기화
2. 스택에서 노드를 꺼낸 후 인접 노드를 다시 스택에 삽입
3. 2단계를 스택에 값이 없을때 까지 반복

*BFS(너비 우선 탐색)

• DFS와 동일하게 완전 탐색을 위한 구현 but 목표 노드까지의 최단 경로를 보장
• queue자료구조를 이용해서 구현
• 시간 복잡도 = O(V+E).  *V=노트 수, E= 간선 수

#백준 2178번 문제 Bfs예시 문제
from collections import deque

N,M=map(int, input().split())
graph=[]

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

def bfs():
    while que:
        x,y=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M and graph[nx][ny]==1:
                graph[nx][ny]=graph[x][y]+1
                que.append((nx,ny))
                             
                
for i in range(N):
    graph.append(list(map(int,input())))

que=deque()
que.append((0,0))
bfs()
print(graph[N-1][M-1])

 

*핵심 이론

• BFS를 시작할 노드를 정한 후 초기화
• 큐에서 노드를 꺼낸 후 꺼낸  노드 인접 노드 다시 큐에 삽입
• 큐에 값이 없을 때 까지 반복