DFS, BFS 알고리즘 정리

- 유형 : 그래프 탐색

- bfs, dfs 정리(기본은 기억해두기) 

• 백준 DFS와 BFS 1260번 문제 참고

# 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V
N, M, V = map(int, input().split()) # 

graph = [[0] * (N+1) for _ in range(N+1)]
visited1 = [0] * (N+1)
visited2 = [0] * (N+1)
for _ in range(M):
    p, q = map(int,input().split())
    
    graph[p][q] = graph[q][p] = 1

def dfs(V):
    visited1[V] = 1

    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)

def bfs(V):
    visited2[V] = 1
    deque=[V]
    while deque:
        V = deque.pop(0)
        print(V, end=' ')
        for i in range(1, N+1):
            if graph[V][i] ==1 and visited2[i] == 0:
                deque.append(i)
                visited2[i] = 1
        

  
dfs(V)
print()
bfs(V)

• 그래프 탐색 알고리즘
  • dfs : 깊이 우선 탐색, 한 놈만 끝까지 팬다 -> 재귀함수가 가장 일반적, 수행 시간에서 초과 발생 가능.
  • bfs : 너비 우선 탐색, 여러 놈을 한대씩 때리면서 가는 유형 -> queue, linkedlist 사용, 시간 복잡도 낮음.
• 대표적 문제 유형
  1. 경로 탐색 유형(최단거리, 시간)
  2. 네트워크 유형(연결)
  3. 조합 유형(모든 조합 만들기)

- 개발자로 취직하기 유튜브 참고