[알고리즘] 깊이/너비 우선 탐색(DFS/BFS) / 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

DFS 관련 연습을 하다가 본 문제로, DFS를 이용해 풀어봤다.

(DFS : 깊이 우선 탐색)

 

해당 문제는 BFS로도 풀 수 있다고 하는데, BFS는 잘 구현하지 못해 그나마 해본 DFS로 구현해봤다.

Backtracking을 이용하려 하였으나 Backtracking을 구현하게 되면 isValid를 체크할 때 시간이 더 들 것 같아서 DFS로만 풀었다.

(근데 풀고나서 다른 사람들 풀이보니 현타온다.)

 

풀이의 핵심은 opCode(연산자)와  numberList를 저장하여 사용하는 방식으로 풀었다.

var count = 0
val opCodeList = listOf("+", "-")
 
fun main() {
 
    val numbers = IntArray(5) { 1 }
    val numberList = IntArray(numbers.size) { 0 }
    val target = 3
 
    dfs(0, numbers, target, numberList)
 
    println(count)
}
 
fun dfs(depth: Int, numbers: IntArray, targetNumber: Int, numberList: IntArray) {
    if (depth == numbers.size) {
        if (targetNumber == numberList.sumBy { it }) {
            count++
        }
        return
    }
 
    for (i in opCodeList.indices) {
        if (opCodeList[i] == "-") {
            numberList[depth] = (numbers[depth] * -1)
        } else {
            numberList[depth] = (numbers[depth] * +1)
        }
 
        dfs(depth + 1, numbers, targetNumber, numberList)
    }
}

depth가 끝까지 진행되었을 때 targetNumber와 같다면 count를 올리고, 아니면 Return되어 다음 opCode 혹은 이전 Depth로 돌아가 계속 연산하는 방식이다.

 

음.. DFS를 알고나니 이런 문제는 핵심만 파악하면 잘 풀 수 있을 것 같긴 하다.