[Swift] 프로그래머스 - 타겟 넘버 ( DFS )

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=swift

프로그래머스

 

간단하게 2차원 배열이 아니라 1차원 배열 DFS 문제를 풀어보았다.

 

DFS란? (Depth First Search )

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점을 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법

 

자바에서 공부했던 코드를 살펴보자

정점 수 : N
인접 행렬 : adjMatrix
방문 체크 배열 : visited

private static void dfs(int current) { //curent 탐색 정점
		visited[current] = true;

		for(int i = 0; i < N; ++i){
				if(adjMatrix[acurrent][i] && !visited[i]){
						dfs(i);
						}
}

 

이제 아래의 문제를 풀어보자

 

 

 

 

 

Swift로 해결한 방식

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    
    func dfs(index : Int, currentSum : Int) -> Int{
        
        
        // 모든 숫자를 사용했으면
        if index == numbers.count{
            return currentSum == target ? 1 : 0
        }
        
        let add = dfs(index : index + 1, currentSum : currentSum + numbers[index])
        let subtract = dfs(index : index + 1, currentSum : currentSum - numbers[index])
        
        return add + subtract
        
    }
    
    return dfs(index:0, currentSum : 0)
}