[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버 코틀린 풀이

 

오늘은 DFS/BFS 알고리즘 문제를 풀어보려 한다.

우선 DFS/BFS 알고리즘에 대해 잘 모르는 분들은 다음 포스팅을 참고하자.

[알고리즘] DFS(Depth-First Search) 알고리즘이란? BFS(Breadth-First Search) 알고리즘이란?

 

 

---

문제는 다음과 같다.

주어진 숫자 배열 numbers에서 각 숫자 앞에 + 또는 -를 붙여서 만든 식의 결과가 target이 되는 경우의 수를 구하자.

 

🧠 문제 접근

DFS(깊이 우선 탐색)를 이용해 모든 경우의 수를 탐색하자.
각 단계마다 현재 숫자를 + 또는 -로 더해가는 방식으로 재귀적으로 탐색한다.

 

---

 

🔍 예제

val numbers = intArrayOf(1, 1, 1, 1, 1) val target = 3

 

 

이 경우, 다음과 같은 식이 가능하다.

-1+1+1+1+1 = 3 
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3 
... 총 5가지 경우

 

 

---

 

💡 코드 구현

class Solution {
    var count = 0

    fun solution(numbers: IntArray, target: Int): Int {
        dfs(numbers, target, 0, 0)
        return count
    }

    fun dfs(numbers: IntArray, target: Int, index: Int, sum: Int) {
        if (index == numbers.size) {
            if (sum == target) {
                count++
            }
            return
        }

        dfs(numbers, target, index + 1, sum + numbers[index])
        dfs(numbers, target, index + 1, sum - numbers[index])
    }
}

 

---

 

✨ 정리

• DFS로 모든 경우의 수를 탐색할 수 있다.
• 배열의 끝까지 도달했을 때 합이 target과 같다면 경우의 수를 1 증가시킨다.
• 이 문제는 재귀와 탐색의 개념을 익히기에 아주 좋다.