dfs c++

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

DFS(Depth-First Search)란?? DFS는 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 정점으로 되돌아와서 다른 방향으로 진행하는 그래프 순회 방법이다. 그래프 순회 방법에는 대표적으로 DFS와 BFS가 있다. DFS 이해하기 DFS 알고리즘을 구현하는 방법에는 인접 리스트를 이용하는 방법, 인접 행렬을 이용한 방법이 있는데 각각 장단점이 존재한다. 인접리스트를 이용했을 때 장점: 모든 노드를 순환하려 할 때 O(N)시간 밖에 걸리지 않는다. 빈 공간이 생기지 않는다. 단점: 인접한 특정 노드를 알고싶을 때 리스트 안에 일일이 찾아봐야한다. 인접 행렬을 이용했을 때 장점: 인접한 특정 노드를 알고싶을 때 2차원 배열에 정보가 저장돼있기 때문에 한 번에 찾..