Swift Algorithm 프로그래머스 Lv2 타겟넘버

지난 BFS글에서 아래 코드를 참고하면,

node.0 (해당 노드의 값) 을 이용하여 해당 노드를 방문한적이 있는지를 판단하였다.

각 노드의 값이 해당 노드의 개수까지 정확히 1씩 증가한다면 해당 풀이가 틀리지 않겠지만 사실 현실은 그렇지 않다.

var graph: [[(Int, Int)]] = [
    [(2, 1), (3, 1)],
    [(1, 1), (4, 1), (5, 1)],
    [(1, 1)],
    [(2, 1)],
    [(2, 1)]
]

var visited: [Bool] = Array.init(repeating: false, count: graph.count)

func dfs(startIndex: Int) {
    visited[startIndex] = true
    
    for node in graph[startIndex] {
        if !visited[node.0 - 1] {
            print(node.0)
            dfs(startIndex: node.0 - 1)
        }
    }
}

dfs(startIndex: 0)

그렇기 때문에 Dictionary를 이용하여, key를 방문하였는지 / 안하였는지를 체킹하는 방식도 소개한다.

위에서 말한 현실은 그렇지 않다 를 만족하는 문제가 있는데, 타겟넘버 문제이다.

해당 문제에서는 [1,1,1,1,1] 과 같은 숫자가 들어왔을때, 이 수의 순서를 유지한 상태로 더하거나 빼서 타겟넘버를 맞추는 개수를 구하는 문제이다.

따라서, [1,1,1,1,-1]과 같은 식의 접근을 할 수 있는데, 이때 위의 방식대로 각 원소를 인덱스에 대입해서 푼다면 오류가 발생하게 된다.

따라서 이번엔, Dictionary의 key를 이용하여 dfs를 진행해보고자 하였다.

+원소, -원소 두가지의 자식 노드를 가진 부모노드가 아래로 numbers의 개수만큼 뻗어나가기 때문에 이를 이용해서 key를 가지는 graph 형태를 만들어주었다.

(다음 원소를 반드시 방문 할 수 있도록 재귀적 형태를 만들어 주어서, visited가 필요 없게 되었다.)

graph[startId] 의 노드들은 결국 최초 방문 노드의 다음 인덱스의 노드 이기 때문에 이를 통해 깊이우선 탐색을 진행할 수 있다.

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var graph: [Int: [(Int, Int)]] = [:]
    var resultList: [[Int]] = []
    
    for (i, n) in numbers.enumerated() {
        graph[i] = [(n, 1), (-n, 1)]
    }
    
    func dfs(startId: Int, path: [(Int, Int)]) {
        if startId == graph.count { 
            resultList.append(path.map { $0.0 })
            return
        }
        
        for node in graph[startId]! {
            let newPath = path + [node]
            dfs(startId: startId + 1, path: newPath)
        }
        
    }
    
    dfs(startId: 0, path: [])
    return resultList.map{ $0.reduce(0, +) }.filter { $0 == target }.count
}

사실 해당 방식은 굉장히 비효율적인 방식이다. 굳이 저장하지 않고 targetNumber의 판단이 가능하지만 resultList에 해당 값들을 대입하게 되어 불필요한 메모리를 사용하게 된다.

다만, 어떤식으로 탐색이 이루어지는지를 볼 수 있기 때문에 우선은 해당 방식으로 구현하였다.

조금 다듬어서, 코드를 작성한다면 다음과 같다.

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var graph: [Int: [(Int, Int)]] = [:]
    var targetNumCount: Int = 0
    
    for (i, n) in numbers.enumerated() {
        graph[i] = [(n, 1), (-n, 1)]
    }
    
    func dfs(startId: Int, path: [(Int, Int)], result: Int) {
        if startId == graph.count { 
            if result == target {
                targetNumCount += 1
            }
            return
        }
        
        for node in graph[startId]! {
            let newPath = path + [node]
            dfs(startId: startId + 1, path: newPath, result: node.0 + result)
        }
        
    }
    
    dfs(startId: 0, path: [], result: 0)
    return targetNumCount
}