[8일차] 05 탐색 : 05-1 깊이 우선 탐색, 05-2 넓이 우선 탐색

함께 푼 문제

[백준 / DFS, BFS] 2606 : 바이러스 (python)

 

깊이 우선 탐색 (DFS)

그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

• 시간 복잡도 : O(V + E)
• 재귀함수 또는 스택으로 구현 가능
• 그래프는 보통 인접 리스트로 나타냄
  • 인접 리스트 : 그래프를 표현하기 위한 방법 중 하나. 그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법.

    

    인접 리스트

• 노드 방문 여부 체크리스트(visited) 필요

 

DFS

파이썬 구현 : 재귀함수

def DFS(v):
    visited[v] = True
    print(v)
    for i in A[v]:
        if not visited[i]:
            DFS(i)

 

넓이 우선 탐색 (BFS)

그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

• 시간 복잡도 : O(V + E)
• 큐로 구현 가능
• 그래프는 보통 인접 리스트로 나타냄
• 노드 방문 여부 체크리스트(visited) 필요
• 경로가 여러 개일 때 최단 경로를 보장

BFS

 

파이썬 구현

def BFS(v):
    q = deque()
    q.append(v)
    visited[v] = True
    while q:
        n = q.popleft()
        print(n)
        for i in A[n]:
            if not visited[i]:
                q.append(i)
                visited[i] = True