[알고리즘] DFS - 깊이 우선 탐색이란?

Intro.

안녕하세요 Pu드로이드 입니다^^

 

취업차.. 코딩테스트 준비를 위해 1일 1백준 알고리즘 풀이를 꾸준히 하고 있는데요!

 

더 나은 문제 접근을 위해 유튜브 바킹독님의 영상으로 알고리즘 기본기를 다질 계획이며,

 

동시에 블로그 포스팅을 통해 정보를 기록하고 공유하려 합니다! 

 

궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!

 

 

---

 

 

DFS

깊이 우선 탐색 - Depth First Search

깊이 우선 탐색 방법 또한 그래프 탐색 방식 중 하나입니다.

 

BFS가 중심을 기준으로 가장 가까운곳부터 탐색하는 방법이였다면,

DFS는 이름답게 깊이를 우선으로 탐색합니다!

 

위 그림과 같이 중심으로부터 임의의 한곳을 정해 

더이상 탐색이 불가할 때 까지 탐색하는 알고리즘이며

 

이를 구현하기 위해 보통 재귀 or 스택을 사용합니다.

 

다음 예시 문제로 이해해보겠습니다.

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

<풀이과정>

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)
}

하나를 발견하면 더이상 탐색이 불가능할 때 까지 탐색 과정을 거치기 위해

재귀 함수를 반복적으로 호출하였습니다!

 

 

 

궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!