목록DFS (12)

땀두 블로그

[백준] 2468번 - 안전 영역

dfs를 활용한 문제이다. 배열을 그릴 때 최대 값을 저장하고, 그 최대값 까지 순환하면서 dfs로 탐색을 진행한다. 진행 시 물의 높이보다 낮은 경우 진행하지않고, 해당 탐색을 진행할 때마다 카운트를 더해 최종 카운트와 현재 저장된 결과값을 비교하여 더 높은 덩어리를 가진 값을 출력하도록 하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p2468 { public static int[][] ary; public static boolean[][] visited; public static int a;..
알고리즘/백준 2022. 3. 23. 08:26
DFS VS 백트래킹

백트래킹(backtracking)이란? 문제를 해결하기 위한 해답을 탐색하는 과정에서 진행 도중에 솔루션을 찾는 과정에서 더 이상 진행을 한다고 해도 탐색을 완료할 수 없는 지점에 도달했을 때 그 경로를 포기하고 이전 단계를 추적하여 되돌아가는(back-tracking) 기법이다. DFS와 백트래킹은 둘다 재귀호출을 이용하여 비슷한 구조로 되어있지만 DFS와 비슷하지만 DFS의 경우 모든 노드를 방문하는 것을 목표로 하고 Back-tracking은 경로에서 더 이상 나아갈 수 없다고 판단하면 해당 경로를 버리고 이전 단계로 다시 돌아와서 탐색한다는 차이가 있다. 백트래킹으로 DATA라는 단어를 탐색하는 경우 DFS로 DATA라는 단어를 탐색하는 경우
알고리즘 2022. 3. 22. 08:10
DFS 예제 코드

public class DFS_EX { static int row, col; static int[][] map; static boolean[][] visit; static int[] dx = { -1, 1, 0, 0 }; static int[] dy = { 0, 0, -1, 1 }; public static void main(String[] args) { Scanner input = new Scanner(System.in); col = input.nextInt(); row = input.nextInt(); map = new int[row][col]; visit = new boolean[row][col]; for(int i = 0; i < row; i++) { for(int j = 0; j < col; j..
알고리즘 2022. 3. 22. 08:09
DFS 개념

그래프 탐색 기법 중 하나로 Depth First Search의 준말로 그대로 번역하면 깊이 우선 탐색이라는 뜻이다. 그래프 탐색은 하나의 정점으로부터 시작해서 해당 노드들이 이어진 모든 정점을 한 번씩 탐색하는 것을 말한다. 너비우선 탐색과는 다르게 깊이(depth)를 우선적으로 탐색하는 탐색 방법이다. 그림으로 간단하게 설명하면 위와 같이 노드들이 있을 때 한 노드의 가장 깊은 곳 까지 탐색하여 A ->​ B ->​ D ->​ E ->​ C -> ​ F ->​ G 순으로 탐색을 하게 된다. DFS의 특징 모든 노드를 탐색하는데 유용한 탐색 방식 코드가 직관적이어서 BFS보다 간단하지만 속도는 느림 위 사진들과 같이 가장 낮은 depth까지 탐색을 하고 최종 depth까지 탐색하면 바로 위의 깊이로 가..
알고리즘 2022. 3. 22. 08:08
[백준] 1780번 - 종이의 수

dfs로 풀 수 있는 문제이다. 종이를 탐색하고 첫 인덱스와 값이 다른 경우 9등분하여 함수 호출하는 부분을 반복하여서 문제를 해결하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p1780 { public static int[][] ary; public static boolean[][] visited; public static int cnt; public static int cnt1; public static int cnt2; public static int a; public static void..
알고리즘/백준 2022. 3. 22. 07:54
Prev 1 2 3 Next