[10주차] DFS&BFS, Greedy 알고리즘, 최소 신장 트리

DFS & BFS

• 그래프 알고리즘으로, 경로를 찾는 문제 시 상황에 맞게 DFS와 BFS를 활용하면 된다.
• 그래프는 정점(node)와 그 정점을 연결하는 간선(edge)로 이루어진 자료구조이며, 그래프를 탐색한다는 것은 하나의 정점에서 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.
• 두 알고리즘 모두 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. (검사하지 않을 경우 무한루프 위험성)

깊이 우선 탐색 (DFS)

• 루트 노드(혹은 임의의 노드)에서 시작해서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법 (미로찾기와 유사)
• 스택 또는 재귀함수로 구현 (순환 알고리즘의 형태)
• 모든 경로를 방문해야 할 경우에 적합
• 시간 복잡도 (V는 정점, E는 간선)
  • 인접 행렬: O(V^2)
  • 인접 리스트: O(V+E)

넓이 우선 탐색 (BFS)

• 루트 노드(혹은 임의의 노드)에서 인접한 노드부터 먼저 탐색하는 방법

• 큐를 이용하여 구현 (해당 노드의 주변부터 탐색해야 하기 때문) → 선입선출(FIFO) 원칙으로 탐색

• 최소비용이 우선일 때에 적합

• 주로 를 찾을 때 사용

  두 노드 사이의 최단 경로

• 재귀적으로 동작x

• 시간 복잡도

  • 인접 행렬: O(V^2)
  • 인접 리스트: O(V+E)

  ---

  Greedy 알고리즘

  • 탐욕 알고리즘

  • 문제 해결을 위해 순간순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

  • 문제의 성질이 동일하게 보존되고, 같은 전략을 반복적으로 사용 가능할 때 적용

    • 앞의 선택이 이후의 선택에 영향을 주지 않을 때
    • 최종 해결 방법이 부분 문제에 대한 해결 방법과 동일한 조건일 때 (지역적, 전역적으로 모두 최적)

  • 장점: 다른 최적 해 계산 알고리즘에 비해 적은 비용 (빠른 속도)

  • 단점: 당장 그 순간의 최적 값을 찾기 때문에 항상 최적 해를 찾는 것은 불가능

  • 문제 해결 방법

    1. 션택 절차: 현재 상태에서의 최적의 해답을 선택
    2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사
    3. 해답 검사: 원래의 문제가 해결됐는지 검사하고, 해결되지 않았다면 다시 선택 절차로 돌아가 위의 과정 반복

    ---

    최소 신장 트리 (Minimum Spanning Tree)

    • 대표적인 알고리즘으로 프림 알고리즘, 크루스칼 알고리즘이 있다.
    • 신장 트리는 그래프 내에 있는 모든 정점을 연결하면서 사이클이 없는 그래프를 의미한다.
    • 최소 신장 트리는 간선들의 가중치의 합이 최소가 되는 신장 트리이다.
    • 특징:
      • 간선의 가중치의 합이 최소여야 한다.
      • n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
      • 사이클이 포함되어서는 안된다.

    프림 알고리즘

    • 최소 신장 트리에 연결된 정점 주변에 있는 간선의 가중치 중 가장 작은 것을 골라 최소 신장 트리를 만드는 방법
    • 동작 원리
      1. 그래프와 비어있는 최소 신장 트리를 만든다.
      2. 임의의 정점을 시작 정점으로 선택하고, 최소 신장 트리의 루트 노드로 삽입한다.
      3. 최소 신장 트리에 삽입된 정점과 이 정점과 인접한 정점의 가중치를 확인하여 가장 작은 가중치를 최소 신장 트리에 삽입한다. (삽입 시 사이클이 형성되지 않도록 함)
      4. 3번 과정을 반복한 후 모든 정점이 최소 신장 트리에 연결되면 종료한다.
    • 프림 알고리즘에서 중요한 것은 최소 가중치를 찾는 것이다.
    • 최소 가중치를 빠르게 찾기 위해서 **힙(Heap)**을 사용한다.
    • 최소 신장 트리에서 정점과 인접한 간선을 (가중치, 정점)으로 힙에 삽입하고, 힙에서 꺼낸 정점과 인접한 정점을 순회하면서 가중치가 최소인 정점을 다시 힙에 추가하면서 힙이 비어있을 때까지 반복한다. (이미 방문한 정점일 경우 트리에 추가x)

    크루스칼 알고리즘

    • 그래프 내의 모든 간선의 가중치를 확인하고, 가장 작은 가중치부터 확인하여 최소 신장 트리를 만드는 방법이다. 탐욕적인(Greedy) 방법을 사용한다.

    • 동작 원리

      1. 선택되지 않은 간선들 중 한다. (모든 간선의 가중치를 오름차순으로 정렬 후)

         최소 가중치인 간선을 선택

      2. 그 간선을 선택했을 때 지금까지 구성된 스패닝 트리에 에만 선택한다.

         사이클이 없는 경우

      3. 총 (까지 반복한다.

         정점의 개수-1)개의 간선이 선택될 때

    • 구성한 스패닝 트리에 사이클이 발생하는지 여부를 판단하기 위해 분리 집합을 사용한다. (분리집합: 서로 공통된 원소를 갖지 않는 집합)

    • 이를 실제로 구현하기 위해선 Union-Find 알고리즘을 사용한다.

      • 각 간선이 스패닝 트리에 추가될 때마다 Parent 관계를 만들어 놓는다.
      • 만약 어떤 간선을 선택했을 때 그 간선의 두 정점이 같은 최상위 Parent를 갖는다면 사이클이 발생함을 의미한다.