3 minute read

나동빈 알고리즘 강의_ DFS, BFS

#dfs #bfs

  • 그래프 탐색 알고리즘 : DFS/ BFS

    • 탐색이란 많은 데이터 중에서 원하는 데이터를 찾는 과정
    • DFS/ BFS는 코테에서 매우 중요
  • 스택 자료구조

    • 선입후출
    • 입구와 출구가 동일한 형태
    • 박스 쌓기로 생각
  • 큐 자료구조

    • 선입선출
    • 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
    • 줄서기로 생각
    • 파이썬은 리스트로 사용하면 시간 복잡도가 올라가므로 무조건 deque사용!
  • 재귀함수

    • 자기 자신을 다시 호출하는 함수 (Recursive Function)

      def recursive_function():
          print('재귀 함수를 호출합니다.')
          recursive_function()
              
      recursive_function()
      
      • 파이썬에서는 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지 만날 수 있다.
      • 제한을 느슨하게 하는 방법도 존재한다. 하지만 보통 코딩테스트에서는 제한 안에서 작동되도록 한다.
    • 재귀 함수의 종료 조건

      • 재귀 함수 문제 풀이에서 재귀 함수의 종료 조건은 반드시 명시해야 한다.
      • 종료 조건이 없으면 함수가 무한히 호출될 수 있다.
      def recursive_function(i):
          # 100번째 호출을 했을 때 종료되도록 종료 조건 명시
          if i == 100:
              return
          print(i, '번째 재귀함수에서',i+1, '번째 재귀함수를 호출합니다.')
          recursive_function(i+1)
          print(i, '번째 재귀함수를 종료합니다.')
              
      recursive_function(1)
      
    • 팩토리얼 구현 예제

      • n! = 1 x 2 x 3 x … x n
      • 수학적으로 0! 과 1! 의 값은 1입니다.
      # 반복적으로 구현한 n!
      def factorial_iterative(n):
          result = 1
          # 1부터 n까지의 수를 차례대로 곱하기
          for i in range(1, n + 1):
              result *= i
          return result
          
          
      # 재귀적으로 구현한 n!
      def factorial_recursive(n):
          if n <= 1:        # n이 1이하인 경우 1을 반환
              return 1
          # n! = n * (n - 1)! 를 그대로 코드로 작성하기
          return n * factorial_recursive(n-1)
          
      # 각각의 방식으로 구현한 n! 출력(n = 5)
      print('반복적으로 구현 :', factorial_iterative(5))
      print('재귀적으로 구현 :', factorial_recursive(5))
      
    • 최대공약수 계산 (유클리드 호제법) 예제

      • 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘

      • 유클리드 호제법이란

        두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.

        이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.

      • 유클리드 호제법 아이디어 그대로 재귀 함수 작성

        • 예시 : GCD(192, 162)

          단계 A B
          1 192 162
          2 162 30
          3 30 12
          4 12 6
          def gcd(a, b):
              if a % b == 0:
                  return b
              else:
                  return gcd(b, a % b)
                      
          print(gcd(192, 162))
          
    • 재귀 함수 사용의 유의 사항

      • 복잡한 알고리즘 간결하게 장성 가능 but 다른 사람이 이해하기 어려워 질 수 있다.
      • 반복문을 통해 동일한 기능 구현 가능
      • 반복문 보다 재귀함수가 유리한 경우, 불리한 경우 모두 존재
      • 함수를 연속적으로 호출하면 메모리 내부에 스택 프레임 쌓인다. 스택을 사용해야 할 때 스택 라이브러리 대신 재귀 함수를 사용하기도 한다.
  • DFS(Depth-First Search)

    • 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

    • 스택 자료구조 이용 ( 혹은 재귀 함수 )

      1. 탐색 시작 노드를 스택에 삽입, 방문처리
      2. 인접 노드에서 방문하지 않은 노드는 스택에 쌓음
      3. 방문한 노드만 존재하면 스택에서 꺼낸다
      4. 위의 2번 과정이 불가할 때까지 반복한다
    • DFS 소스코드 예제

      def dfs(graph, v, visited):
          # 현재 노드를 방문 처리
          visited[v] = True
          print(v, end = ' ')
          # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
          for i in graph[v]:
              if not visited[i]:
                  dfs(graph, i, visited)
                      
      # 각 노드가 연결된 정보를 표현 ( 2차원 리스트 )
      graph = [
          [],
          [2, 3, 8],
          [1, 7],
          [1, 4, 5],
          [3, 5],
          [3, 4],
          [7],
          [2, 6, 8],
          [1, 7]
      ]
          
      # 각 노드가 방문된 정보를 표현 ( 1차원 리스트 )
      visited = False * 9
          
      # 정의된 DFS 함수 호출
      dfs(graph, 1, visited)
      
  • BFS(Breadth-First Search)

    • 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색하는 알고리즘

    • 큐 자료구조 이용

      1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
      2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입, 방문처리
      3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
    • BFS 소스코드 예제

      from collections import deque
          
      # BFS 메서드 정의
      def bfs(graph, start, visited):
          # 큐 구현을 위해 deque 라이브러리 사용
          queue = deque([start])
          # 현재 노드를 방문 처리
          visited[start] = True
          # 큐가 빌 때까지 반복
          while queue:
              # 큐에서 하나의 원소를 뽑아 출력하기
              v = queue.popleft()
              print(v, end=' ')
              # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
              for i in graph[v]:
                  if not visited[i]:
                      queue.append(i)
                      visited[i] = True
                          
      # 각 노드가 연결된 정보를 표현 (2차원 리스트)
      graph = [
          [],
          [2, 3, 8],
          [1, 7],
          [1, 4, 5],
          [3, 5],
          [3, 4]
          [7],
          [2, 6, 8],
          [1, 7]
      ]
          
      # 각 노드가 방문된 정보를 표현 ( 1차원 리스트 )
      visited = [False] * 9
          
      # 정의된 BFS 함수 호출
      bfs(graph, 1, visited)
      

Updated: