알고리즘/DFS & BFS
[CS] DFS와 BFS의 원리와 구현 방식 (JAVA)
DFS DFS(Depth-First Search)는 깊이 우선 탐색이라고 부른다. 한 경로로 최대한 깊숙하게 들어가서 탐색한 후 다시 돌아가 다른 경로를 탐색하는 방식 일반적으로 재귀함수를 이용하여 구현하며 Stack을 이용하여 구현하기도 함 구조상 Stack Overflow에 유의해야 함 DFS 활용 : 백트랙킹, 단절선 찾기, 위상정렬, 사이클 찾기 등 DFS 구현 1. 체크인 2. 목적지인가? 3. 연결된 곳을 순회 4. 갈 수 있는가? 5. 간다 6. 체크아웃 static int[][] graph; static boolean[] visited; static void dfs(int index) { // 1. 체크인 visited[index] = true; // 2. 목적지인가? if (종료조건) {..
