Intro.
안녕하세요 Pu드로이드 입니다^^
취업차.. 코딩테스트 준비를 위해 1일 1백준 알고리즘 풀이를 꾸준히 하고 있는데요!
더 나은 문제 접근을 위해 유튜브 바킹독님의 영상으로 알고리즘 기본기를 다질 계획이며,
동시에 블로그 포스팅을 통해 정보를 기록하고 공유하려 합니다!
궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!
DFS
깊이 우선 탐색 - Depth First Search

깊이 우선 탐색 방법 또한 그래프 탐색 방식 중 하나입니다.
BFS가 중심을 기준으로 가장 가까운곳부터 탐색하는 방법이였다면,
DFS는 이름답게 깊이를 우선으로 탐색합니다!
위 그림과 같이 중심으로부터 임의의 한곳을 정해
더이상 탐색이 불가할 때 까지 탐색하는 알고리즘이며
이를 구현하기 위해 보통 재귀 or 스택을 사용합니다.
다음 예시 문제로 이해해보겠습니다.
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
<풀이과정>
var inputArr = arrayOf(intArrayOf())
var visitArr = arrayOf(booleanArrayOf())
var size = 0
fun main(){
// 0,0에서부터 n,m까지 하나씩 지나감
// 가다가 0이 아닐경우 bfs로 체크
// 끝나면 단지 번호와 단지 개수를 맵에다 체크
size = readln().toInt()
val map = mutableMapOf<Int, Int>()
var bg = 1
inputArr = Array(size){ intArrayOf() }
visitArr = Array(size){ BooleanArray(size){false} }
repeat(size){
inputArr[it] = readln().chunked(1).map { it.toInt() }.toIntArray()
}
for(i in inputArr.indices)
for(k in inputArr.indices)
if(inputArr[i][k] == 1) {
map[bg] = bfs(i, k, 0)
bg++
}
println(map.size)
val dapList = mutableListOf<Int>()
map.forEach{dapList.add(it.value)}
dapList.sorted().forEach{println(it)}
}
fun bfs(y: Int, x: Int, count: Int): Int{
if(y<0 || x<0 || y>=size || x>=size) return 0
if(inputArr[y][x] == 0) return 0
if(visitArr[y][x]) return 0
visitArr[y][x] = true
inputArr[y][x] = 0
return 1 + bfs(y+1,x,count) + bfs(y-1,x,count) + bfs(y,x+1,count) + bfs(y,x-1,count)
}
하나를 발견하면 더이상 탐색이 불가능할 때 까지 탐색 과정을 거치기 위해
재귀 함수를 반복적으로 호출하였습니다!
궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!
'알고리즘' 카테고리의 다른 글
| [알고리즘] BFS - 너비 우선 탐색이란? (0) | 2023.12.21 |
|---|---|
| [알고리즘] 자료구조 스택, 큐, 덱 (0) | 2023.12.13 |
| [알고리즘] 배열, 연결리스트 with Kotlin (0) | 2023.12.12 |
| [알고리즘] 시간복잡도, Kotlin 자료형 (0) | 2023.12.11 |