DFS동작방식
DFS(깊이우선탐색)은 그래프 데이터 구조에서 노드를 탐색하는 한 가지 방법이다. 이 알고리즘은 그래프의 깊이를 최대한 깊게 파고들어서 탐색하는 특징이 있다. DFS는 스택 또는 재귀함수를 사용하여 구현되는데, DFS의 동작을 살펴보면
- 시작 노드를 방문
- 현재 노드와 이웃한 노드 중에서 방문하지 않은 노드가 있다면 그 노드로 이동.
- 더 이상 방문하지 않은 이웃 노드가 없을때까지 2번 반복.
- 더 이상 진행할 수 없으면 이전 노드로 돌아가서 2번 반복.
이렇게 설명하면 DFS가 어려워보인다.. DFS를 이용해서 문제를 풀며 예로 설명해보겠다.
DFS활용문제
programmers에 타겟 넘버 라는 문제가 있다.
https://school.programmers.co.kr/learn/courses/30/lessons/43165
이 문제에서 만약 {1,1,1}이 배열에 들어있는 숫자로 target:1 을 목표로 한다면 모든 경우의 수를 구해야 한다.
+1+1+1 -> 3 target아님
+1+1-1 -> 1 target
+1-1+1 -> 1 target
+1-1-1 -> -1 target아님
-1+1+1 -> 1 target
-1+1-1 -> -1 target아님
-1-1+1 -> -1 target아님
-1-1-1 -> -3 target아님
이렇게 해서 타겟의 개수 3을 구해줘야 한다.
하나하나 일일이 써보면 이렇게 되는거지 위에서 설명한 방식대로 풀이한 것이다. 부호와 인덱스에 대해서만 생각해보면 부호는 +,- 둘중하나이고, index는 최대 0부터 2까지만 존재한다. 그렇다면 먼저 부호가 +일때부터 계산을 해주고 그뒤로 제일 뒤에있는 인덱스부터 부호를 -로 바꿔주면서 계산을 해주면 된다.
작성한 코드로 보면
class Solution{
var numbers = intArrayOf()
var target = 0
var answer = 0
fun solution(numbers: IntArray, target: Int): Int {
answer = 0
this.numbers = numbers
this.target = target
dfs(0,0)
return answer
}
fun dfs(index:Int, sum:Int){
if(index == numbers.size){
if(sum == target) answer ++
return
}
dfs(index+1, sum+numbers[index])
dfs(index+1, sum-numbers[index])
}
}복잡해 보이지만 복잡하다... 처음이라그런가.. ㅎㅎ
필요할때마다 매번 배열과 target을 가져오면 부담되니 새로운 배열과target을 만들어서 새로 선언해준다. 그후 this를 이용해서 해당 배열과 target에 값을 넣어 저장해준다. 그리고 dfs함수를 만들어서 (0,0)을 넣어주며 재귀를 시작해준다.
여기서 들어가는 두개의 파라미터는 인덱스와 지금까지 값들의 총합인 sum이다.
만약에 현재 들어간 dfs의 index값이 배열의 크기와 같다면 배열의 제일 끝 원소까지 비교가 끝났다는 뜻이니 바로 return해주고 만약 지금까지의 sum값이 내가 구하고자하는 target과 같다면 answer++를 해주고 return해주었다.
같지 않다면 dfs에(index+1, sum+numbers[index])를 넣어주는데, 이 뜻은 앞서 설명한 2번과 같은 뜻으로, 현재 노드에서 인접한 노드로 들어가며 현재 sum에서 배열의 index값을 더해준 값을 다시한번 불러오며 지금까지의 합을 보내준다.
이렇게해서 반복적으로 dfs를 호출하며 배열의 끝까지 모든 원소들을 더하고, 빼주며 값을 구해줬다.
DFS사용시기
모든 값을 끝까지 들어가서 다 비교해보는 이런 DFS가 항상 사용될 수 있는건 아니다. 이건 무식하게 모든 경우의수를 다 따져보는 알고리즘으로, 시간복잡도가 굉장히 크다.
보통은 테스트케이스에서 최악의 경우의수를 생각해보고, 그 경우가 대략 500만번 미만이라면 충분히 DFS를 사용해도 괜찮다고 생각하면되는데, 이문제의 경우 numbers배열에 최대 20개의 숫자가 들어올수 있고, 그에따른 경우의 수는 2^20이 최악의 경우의 수가 되고, 이는 약 100만번정도가 된다.(2^22이 약 400만번)
그렇다면 충분히 재귀함수를 이용해서 완전탐색을 진행해도 시간복잡도에는 문제가 없다고 생각하면 된다.
다른 DFS문제들
https://school.programmers.co.kr/learn/courses/30/parts/12421
