[알고리즘] 그래프 탐색 알고리즘, BFS와 DFS

그래프와 탐색 알고리즘

• 그래프는 대상들의 관계를 나타낼 때 적합한 자료구조로 대상 나타내는 node 또는 vertex들과 그들의 연결 관계를 나타내는 Edge로 표현할 수 있다.
• 그래프는 edge가 탐색할 수 있는 방향의 존재 여부와 가중치의 여부에 따라 크게 네 가지 종류로 구분할 수 있다.
  • 무향 그래프 : edge의 방향이 없는 그래프
  • 유향 그래프 : edge에 방향이 있는 그래프
  • 가중치 무향 그래프 : edge에 방향은 없으나 가중치가 있는 그래프
  • 가중치 유향 그래프 : edge에 방향과 가중치가 있는 그래프
• 행렬의 행은 출발하는 node의 숫자, 열을 도착하는 node의 숫자로 그래프를 표현할 수 있다.
• 아래의 예는 유향 그래프를 행렬로 표현한 것을 나타낸 예시이다.
  • 1번 node는 2와 3으로 연결되어 있어 행렬의 (1,2), (1,3)에 연결되었다는 의미로 1을 표시하고 그 외 연결되지 않은 node의 자리는 0으로 표시한다.
    

    

• 그래프를 탐색하며 어떤 문제의 해를 구할 때 모든 node를 방문하며 탐색해야하는 과정이 필요하다.
• 그래프의 모든 node를 빠짐없이 탐색하는 완전 탐색 알고리즘으로는 Breadth First Search(BFS)와 Depth First Search(DFS) 방법이 있다. 두 알고리즘은 한 노드를 visit하고 expand할 때 우선 순위를 두는 방식에 따라 구분된다.

Breadth-First Search(BFS)

• BFS는 방문한 노드에 인접한 노드들을 우선 방문하도록 하는 알고리즘이다.
• queue 자료구조를 사용해 visit과 expand를 모든 노드를 방문해 탐색하지 않은 노드가 없을 때 까지 반복하는 방식으로 구현한다.
• BFS 알고리즘은 다음과 같은 순서로 진행된다.
  1. 탐색 시작 node를 queue에 push
  2. queue가 empty일 때까지 반복
     1. queue의 가장 앞 요소를 pop
     2. pop 된 node를 처리하는 코드
     3. 해당 노드에 인접하면서 아직 방문하지 않은 node를 queue에 push & 방문 처리
• 나는 BFS로 문제를 풀 때, 전체를 구현하기 전에 전체 틀을 구성하는 코드를 먼저 작성하고 구현해야하는 내용을 주석으로 표시해놓고 풀이한다.
• 문제를 보고 python으로 BFS 알고리즘을 구현해야겠다는 판단했다면 전체 코드를 짜기 전에 아래의 코드를 먼저 작성한 후 빈 부분을 채워나간다.

from collections import deque

# queue 생성
q = deque()

# 시작 점 enqueue code 넣기

while (q): # q에 요소가 남아 있다면 반복
    cur = q.pop()

    for ~~ :# 인접한 node 탐색 code  
        # do sth
        pass

• 아래는 간단한 tree 형태의 그래프를 BFS로 탐색하는 과정을 보여준다.

• a : 탐색을 시작하는 1번 노드를 queue에 push
• b : queue에 가장 앞에 있는 1번 node를 pop해 방문하고 인접한 node 2, 3을 queue에 push
• c : 2번 node를 queue에서 pop, 인점한 node 4, 5를 queue에 push
• d : 3번 node를 queue에서 pop, 인접한 node 6을 queue에 push
• e : 4번 node를 queue에서 pop, 인접한 node는 없기 때문에 push할 node는 없음
• f : 5번 node를 queue에서 pop, 인접한 node는 없기 때문에 push할 node는 없음
• g : 6번 node를 queue에서 pop, 인접한 node는 없기 때문에 push할 node는 없음
• queue가 비어있기 때문에 탐색을 종료

관련 문제

2022.08.02 - [알고리즘 공부/백준 문제풀이] - [백준 python] 14502번 연구소

2022.09.21 - [알고리즘 공부/백준 문제풀이] - [백준 python] 14499번 주사위 굴리기

2022.08.15 - [알고리즘 공부/백준 문제풀이] - [python 백준] 23288번 주사위 굴리기 2

2022.09.24 - [알고리즘 공부/백준 문제풀이] - [python 백준] 1012번 유기농 배추

DFS

• DFS는 방문한 노드에 인접한 노드 중 방문하지 않은 노드를 우선 탐색하도록 하는 알고리즘이다.
• DFS는 stack 자료구조를 사용해 구현할 수 있지만 구현의 편리함 때문에 재귀 형태로 구현하는 것이 일반적이다.
• DFS 알고리즘은 다음과 같은 순서로 진행된다.
  1. 가장 처음 방문할 노드를 stack에 넣는다.
  2. stack이 empty일 때까지 반복
     1. 해당 노드에 인접한 node 중 방문하지 않은 node를 방문하고 stack에 push / 방문하지 않은 node가 없다면 stack에서 pop
     2. stack의 가장 위에 있는 ndoe로 이동
• 나는 아래 뼈대 코드를 기억하고 문제 풀이를 한다. BFS에 비해 문제에 따라 풀이를 달리하는 경우가 많아 재귀 함수의 뼈대만 기억하고 풀이하는 편이다.

def DFS():
    if (leaf node 도달 조건):
        # do sth
        return

    for node in (인접한 node):
        # 방문 표시
        DFS(node)
        # 방문 표시 해제

• 아래는 BFS의 예와 같은 tree 형태의 그래프를 DFS로 탐색하는 과정을 보여준다.

• a : 탐색을 시작하는 1번 노드를 stack에 push
• b : stack의 가장 위에 있는 1번에 인접한 방문하지 않은 2번 node를 방문하고 stack에 push
• c : stack의 가장 위에 있는 2번에 인접한 방문하지 않은 3번 node를 방문하고 stack에 push
• d : stack의 가장 위에 있는 3번에 인접한 방문하지 않은 node가 없으므로 stack에서 pop
• e : stack의 가장 위에 있는 2번에 인접한 방문하지 않은 4번 node를 방문하고 stack에 push
• f : stack의 가장 위에 있는 4번과 2번에 인접한 방문하지 않은 node가 없으므로 stack에서 pop
• g : stack의 가장 위에 있는 1번에 인접한 방문하지 않은 5번 node를 방문하고 stack에 push
• h : stack의 가장 위에 있는 5번에 인접한 방문하지 않은 6번 node를 방문하고 stack에 push
• i : stack의 가장 위에 있는 6번, 5번과 1번에 인접한 방문하지 않은 node가 없으므로 stack에서 pop
• stack이 비어있기 떄문에 탐색을 종료

관련 문제

2022.08.02 - [알고리즘 공부/백준 문제풀이] - [백준 python] 14502번 연구소

2022.07.31 - [알고리즘 공부/백준 문제풀이] - [백준 python] 14888번 연산자 끼워넣기

2022.08.05 - [알고리즘 공부/백준 문제풀이] - [백준 python] 14889번 스타트와 링크

 

조금 더 생각해보기

• 문제를 효율적으로 해결하기 위해 조건을 잘 분석해 탐색이 필요 없는 노드는 탐색하지 않도록 하는 가지치기 방법을 적용해 문제 풀이 효율을 높힐 수 있다.