🍒 Chae-ri Dev 🍒

BFS(Breadth First Search)BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 탐색하는 알고리즘이다. BFS를 구현할 때는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. # 동작 방식1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. deque 라이브러리 사용 => 시간 복잡도 O(N)일반적으로 bfs가 더 빠르다. from collections import deque# BFS 메서드 정의def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 dequ..

대표적인 탐색 알고리즘인 DFS와 BFS는 스택과 큐, 재귀 함수를 이용하여 정리할 수 있다. DFS(Depth First Search)DFS는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프는 다음과 같이 두 방식으로 쓰일 수 있다.1. 인접 행렬 방식INF = 999999999 #무한의 비용 선언# 2차원 리스트를 이용해 인접 행렬 표현graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0]]print(graph)# [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]2. 인접 리스트 방식# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현graph = [[] for _ in r..