[Algorithms] DFS / BFS

탐색 알고리즘 DFS / BFS DFS(Depth First Search) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 = 최대한 멀리 있는 노드를 우선으로 탐색 그래프 : 노드(정점)와 간선으로 표현됨! → 그래프: 하나의 노드를 시작으로 다수의 노드를 방문하는 것 → 두 노드가 간선으로 연결되어 있으면 “두 노드는 인접하다”고 표현 프로그래밍에서 그래프는 2가지 방식으로 표현할 수 있음 1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 → 파이썬에서는 2차원 리스트로 구현! INF = 99999999999 # 연결이 되어 있지 않은 노드끼리는 무한의 비용 # 2차원 리스트를 이용해 인접행렬 표현 graph = [ [0,7,5], [7,0,INF], [5..
Algorithms | 자료구조 2023. 11. 5. 20:01
1