파이썬 - 알고리즘(DFS,BFS)

• 그래프
  • 관계를 표현하는 구조
    • ex) 도시와 도시를 연결하는 도로, 사람 인맥 관계, 컴퓨터 네트워크 등
  • 노드(Node)와 엣지(Edge)로 구성된 자료 구조
    • 노드(=정점, Vertex) : 하나의 데이터 단위를 나타내는 객체
    • 엣지(간선) : 두 노드 간의 연결 관계를 나타내는 데이터(연결선)
    • 두 노드 사이에 엣지가 있으면, [ 두 노드는 인접해 있다] 라고 표현함
  • 그래프 관련 용어
    • 차수(degree) : 하나의 노드에 연결된 엣지의 수
    • 경로(path) : 한 노드에서 다른 노드까지 가는 길 (노드들의 순서)
  • 그래프의 수학적 표현
    • G = (V,E)
      • V : 노드의 집합
      • E : 두 노드를 연결하는 간선의 집합

그래프의 종류

• 무방향 그래프(undirected graph)
  • 두 노드를 연결하는 엣지에 방향이 없는 그래프
• 방향 그래프(directed graph)
  • 엣지에 방향이 있는 그래프
• 가중 그래프(weighted graph)
  • 노드를 연결하는 엣지에 가중치(weight)를 부여한 그래프
    • 가중치: 한 지점에서 다른 지점으로 이동하는데 필요한 비용이나 시간 등
• 파이썬에서 어떤 관계를 표현할 때 적합한 문법 => 딕셔너리
  • 키(key) : 노드
  • 값(value) : 키와 연결된 노드 리스트

 

DFS(Depth First Search)

• 깊이 우선 탐색
  • 노드에 연결된 모든 엣지를 방문하지 않고, 특정 1개의 엣지를 계속 따라 노드들을 방문하다가 더이상 다른 노드를 방문할 수 없는 노드에 이르면, 다시 가장 가까운 분기점으로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법
  • 스택을 이용해서 구현
• 사용 예시
  1. 미로 탐색 : 출구를 찾을 때 한 길을 끝까지 가보고, 막히면 돌아와 다른 길을 탐색하는 방식으로 활용
  2. 백트래킹(Backtracking) : 경우의 수를 모두 탐색하는 문제에 유용
  3. 그래프 연결 요소 찾기 : 한 정점에서 시작해서 연결된 모든 정점을 방문하면 하나의 연결 요소를 찾을 수 있다.
  4. 위상 정렬(Topological Sorting) : DFS를 이용하여 방향성 있는 비순환 그래프(DAG)에서 순서를 결정
     ex) 작업 스케줄링 등
• 동작 방식
  • 방문(탐색)할 노드를 담을 스택(Stack) 자료형 생성
  • 각 노드가 방문한 노드인지를 구분할 수 있는 리스트 생성
  • 탐색 시작 노드(첫번째노드)를 스택에 삽입
  •  방문할 노드를 스택에서 하나씩 꺼내기
  •  스택에서 꺼낸 노드가 방문한 노드가 아니면, 그 인접 노드를 스택에 삽입하고 방문 처리
  • 스택에 방문할 노드가 남지않을때까지 4~5의 과정을 반복
• DFS 함수 만들기

BFS(Breadth First Search)

• 너비 우선 탐색
  • 노드에 인접한 모든 엣지를 따라 노드에 방문하고, 다시 방문한 노드에 인접한 모든 엣지를 따라 노드에 방문하는 과정을 반복적으로 수행하며 탐색하는 방법
  • 큐 이용 구현
• 사용 예시
  1. 최단 경로 찾기(가중치 없는 그래프)
     • 한 지점에서 다른 지점까지의 최단 경로를 찾을 때 사용.
     • 예: 미로에서 최단 거리 찾기, 지도에서 최소 이동 경로 찾기
  2. 소셜 네트워크 분석
     • 특정 사람으로부터 특정 단계(예: 친구의 친구)를 탐색하는 데 활용.
     • 예: 페이스북에서 친구 추천 기능
  3. 웹 크롤링(Web Crawling)
     • 인터넷의 링크 구조를 따라 탐색할 때, 가까운 페이지부터 순차적으로 방문하는 방식으로 BFS가 사용.
  4. 데드락 탐지(Deadlock Detection)
     • 운영체제에서 프로세스 간의 자원 할당 상태를 그래프로 나타내고, 교착 상태(Deadlock)가 발생하는지 확인하는 데 사용.
  5. 네트워크 전파 분석
     • 바이러스 전파, 정보 확산 등의 문제에서 특정 노드에서 시작해 얼마나 빠르게 확산되는지를 분석하는 데 사용
• 동작 방식
  1. 방문(탐색)할 노드를 담을 큐(Queue) 자료형 생성
  2. 각 노드가 방문한 노드인지를 구분할 수 있는 리스트 생성
  3. 탐색 시작 노드(첫 번째 노드)를 큐에 삽입
  4. 방문할 노드를 큐에서 하나씩 꺼내기 (삽입된 순서대로)
  5. 큐에서 꺼낸 노드가 방문한 노드가 아니면, 그 인접 노드를 스택에 삽입하고 방문 처리
  6. 큐에 방문할 노드가 남지 않을 때까지 4~5의 과정을 계속 반복

• BFS 동작 그림