dfs

그래프의 탐색 대표적인 그래프 탐색인 DFS, BFS에 대해서 알아보자. 그래프 탐색의 목적은 임의의 정점에서 시작해서 연결되어있는 모든 정점들을 한 번씩 방문하는 것이다.! 1. DFS (Depth First Search) : 깊이 우선 탐색 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아가서 모든 정점을 방문한다. (재귀를 사용할 수도 있다!) 이 그래프에 dfs를 사용해보자. 1에서 시작하고 어떤 정점을 방문하면 스택에 넣고 check[i] 에 1을 표시하자. 현재 정점 : 1 순서 : 1 스택 : 1 i 1 2 3 4 5 6 check[i] 1 0 0 0 0 0 1 다음에 갈 수 있는건 2, 5 둘 중에 하나로 가면 된다. 2로 가보자 현재 정점 : 2 순서 ..