목록깊이 우선 탐색 (1)

If at first you don't succeed, try again

[알고리즘] DFS(깊이 우선 탐색)(Python)

* 개요 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. 그래프는 노드와 간선으로 표현되며, 이 때 노드를 정점이라고 말한다. 그래프 탐색이란, 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접한다.'라고 표현한다. * 인접 행렬 먼저 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같이 연결된 그래프를 인접 행렬로 표현할 때 파이썬에서는 2차원 리스트로 구현할 수 있다. 연결이 되어 있지 않은 노드끼리는 무한의 비용(INF)이라고 작성한다. 실제 코드에서는 논리적으로 정답이 될 수 없는..
Computer Science/알고리즘(Python) 2022. 11. 16. 17:10
이전 Prev 1 Next 다음