개발 #알고리즘 #자료구조

[알고리즘] DFS/BFS

DFS DFS(Depth-First Search)는 깊이 우선 탐색 알고리즘이다. 그래프에서 깊은 부분을 우선으로 탐색하는 것이다. 그래프가 그럼 뭘까? 그래프는 Node(혹은 정점이라고 부르기도함(vertex))와 Edge(간선)로 표현된다. 예를 들어 노드를 장소, 간선을 거리라고 생각할 수도 있다. 약국에서 병원까지의 거리를 3km, 약국에서 학교를 5km라고 한다면 아래 이미지처럼 표현할 수 있다. 약국 병원 학교 약국 0 3 5 병원 3 0 무한 학교 5 무한 0 ※ 연결되지 않은 노드는 무한으로 표현한다 그래프는 두가지 방식으로 표현된다. 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현 인접 리스트 : 리스트로 그래프의 연결관계를 표현 인접행렬(Adjacency Matrix) INF= 9..