코딩테스트에서 가장 많이 나오는 문제가 바로 DFS이다. (BFS보다 더 많이 나옴)
DFS 개념: 깊이 우선 탐색으로 인접한 노드 중 하나를 골라서 탐색을 하고, 또 그 노드의 인접한 노드 중 하나를 골라서 탐색해나감.
1
2 3
4 5
이런식으로 그래프가 있으면 1->2->4->5->3 순서로 탐색이 진행된다.
이 때, 1의 인접 노드는 2와 3이 있는데 이 순서는 문제에 주어진 기준에 따라 변경할 수 있다.
푸는 방법:
앞에서 DFS 개념을 설명할 때 인접한 노드 중 하나를 골라서 탐색하고, 또 그 노드 중 하나를 골라서 탐색해 나가는 방법이라고 했는데, 사실 이 개념 설명에 힌트가 있다. 바로 문장 자체가 반복된다는 점인데, 이 반복에서 재귀를 떠올릴 수 있다. 재귀는 stack이 기반이므로 당연히 stack으로도 풀 수 있지만, 재귀로 푸는 것이 훨씬 편하다.
프로그래머스 타겟넘버라는 문제를 통해 푸는 방법을 알아본다.
****** 반드시 인접 행렬 혹은 인접 리스트를 만들어야 함. ******
예를 들어 위 예시를 들었던 그래프를 보고 생각해보면
1 -> 2, 3
2 -> 4, 5
가 된다.
다만, 만약 모든 인접 케이스가 동일할 경우 인접리스트를 해당 케이스가 선언된 배열로 간추려서 선언할 수도 있다.
(아래 타겟넘버 풀이에 구체적인 예시가 나옴)
기본 틀:
func main(){
}
func dfs(*1*){
if{
종료조건
return
}
for(*2*){
작업*3*
dfs(*1*)
작업 원복*3*
}
}
DFS를 작성할 때 가장 많이 헷갈리는 부분이 기본틀에서 *1*과 *2*를 작성하는 부분이다.
1에서 문제가 되는 부분은 바로 dfs가 수행될때마다 변경되고 상태가 유지되어야 하는 값에 대한 처리인데, 포인터를 이용하는 것과 전역변수를 사용하는 두 가지 방법이 있다. 포인터를 사용하는 방법을 추천한다. (알고리즘만을 위해서라면 전역변수도 문제는 없지만 실제 코딩을 할 때 변수에 대한 접근성 때문에 전역변수는 최대한 사용하지 않는다.)
2에서는 인접리스트의 길이가 범위로 들어간다. (인접리스트 혹은 행렬을 반드시 만들어야 하는 이유. 이 for문의 범위에 인접리스트가 들어간다는 점만 기억하면 DFS는 어려울 것이 없다.)
아래가 실제로 타겟넘버에 적용한 DFS 풀이이다.
이 문제를 구글링해보면 대부분 for문 안에서 DFS를 두 번 사용하여(+, -) 문제를 해결하는데 해당 방식은 직관적으로 이해하기가 매우 어렵다. 하지만 앞서 말한 인접리스트를 생각해서 for문 및 종료조건을 제어한다면 공식에 의해 상당히 쉽게 풀 수 있다.
인접리스트가 들어가야하는 for문에 1, -1이라는 cadidates 배열을 만들어 for문을 돌리는데 이 문제의 경우 1과 -1이 모든 노드마다 접근 가능하기 때문에 인접리스트를 그냥 1, -1로 놓고 이를 종료조건에서 제어해도 상관이 없다.
func solution(numbers []int, targetNum int) int {
candidates := []int{1, -1}
target := []int{}
count := 0
testdfs(numbers, candidates, &target, 0, targetNum, &count)
return count
}
func testdfs(numbers []int, candidates []int, target *[]int, start int, targetNum int, count *int) {
if len(*target) == len(numbers) {
sum := 0
for i:=0; i<len(*target); i++ {
sum = sum + (*target)[i]
}
if sum == targetNum {
*count = *count + 1
}
return
}
for i:=0; i<len(candidates); i++ {
*target = append(*target, numbers[start]*candidates[i])
testdfs(numbers, candidates, target, start+1, targetNum, count)
*target = (*target)[:len(*target)-1]
}
}