안전 영역
-
백준 2468번 안전 영역 [DFS] :: 마이구미알고리즘 풀이/그래프 2017. 6. 18. 22:48
이번 글은 백준 알고리즘 문제 2468번 "안전 영역" 을 다뤄본다.정올 초등부에서 출제된 문제이다.초등부이지만, 정답률은 30%인 것을 볼 수 있다.DFS, BFS - http://mygumi.tistory.com/102 문제 접근은 DFS 또는 BFS를 활용할 수 있다.기본적인으로 DFS 및 BFS 기본 지식을 가지고 있다면 충분히 풀 수 있다.여기서는 DFS를 통해 문제를 풀어보겠다. 위 그림은 높이가 4와 6의 경우를 나타내고 있다. 흰색 영역의 수를 찾는 문제가 된다.그래프에서는 이 영역을, 연결 요소의 개수라고 볼 수 있다.즉, DFS 탐색이 이루어지는 횟수 중 가장 큰 수가 정답이 된다. 높이를 1부터 100까지 경우 각각 DFS 탐색을 하면 된다. public static void dfs(..