[프로그래머스] Swift - 모두 0으로 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/76503

프로그래머스

 

2023.09.06 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제를 제대로 이해하는 것이 중요했습니다!!

1. 트리가 주어진다.
2. 임의의 연결된 두 점을 골라서 한쪽은 1 증가, 다른 한쪽은 1 감소시킨다.
3. 2번의 행동을 반복하여 모든 점들의 가중치를 0으로 만들 때 2번의 행동을 몇번 수행해야 하는지 최솟값을 리턴
4. 불가능한 경우는 -1을 리턴

단순해 보이면서도 복잡합니다.

우선 1번 조건부터 조심해야 합니다.

문제에서 제공하는 edges 데이터를 집접 그려보면 트리 구조가 맞지만 주어진 정보 자체는 트리가 아닌 그래프입니다.

이게 무슨 의미냐면 edges가 [[0,1], [1, 2]] 로 주어졌다면 보통

(0: 부모, 1: 자식), (1: 부모, 2: 자식)

으로 생각하기 쉽지만 그렇지 않습니다.

 

(0: 자식, 1: 부모), (1: 부모, 2: 자식)

처럼 순서 없이 데이터를 제공하고 있습니다.

 

따라서 edges는 두 점이 연결되었다는 정보는 알 수 있지만 어떤것이 부모이고 어떤 노드가 Root인지 알 수 없습니다.

즉, 그냥 그래프로 주어졌는데 이 그래프를 그려보면 무조건 트리라는 것이 문제의 조건입니다.

 

2번 조건인 "임의의 연결된 두 점을 골라서 한쪽은 1 증가, 다른 한쪽은 1 감소시킨다." 는 다른 말로 해석하면 한쪽 노드의 가중치를 다른쪽 노드로 옮길 수 있다는 것입니다.

이렇게 연결되어 있다면 5의 가중치를 연결된 -2의 가중치를 가진 노드에게 넘겨서 +5를 해줄 수 있습니다.

이렇게 말이죠!

 

4번 조건인 불가능한 상태에서는 -1을 리턴하는 것은 모든 노드의 가중치를 더했을 때 0이 아니라면 -1을 리턴하라는 의미와 같습니다. 

가중치를 넘겨주는 작업만이 가능한데 이것은 결국 가중치끼리 더하는 것과 같습니다. 모두 더했는데 0이 아니라면 수천번 가중치를 조정해도 모든 노드가 0이 되는 상황은 발생하지 않습니다.

 

 

이제 이렇게 문제를 제대로 파악하고 다시 아이디어를 떠올려 보았습니다.

우선, 문제에서 굳이 트리라고 제공한 이유가 있을 것 같았습니다.

또한 한쪽 노드의 가중치를 연결된 노드로 옮긴다는 아이디어도 활용해야 했습니다.

 

 

결과적으로 가중치를 옮기는 작업을 최소화 하면서 모든 노드를 0으로 만드는 방법은 Leaf 노드에서 시작하여 자신의 부모 노드에게 자신의 가중치를 넘겨주면 됩니다. (넘겨준다 == 더한다)

 

트리가 위와 같다면

이렇게 초록색 화살표 방향처럼 아래의 노드에서 위의 노드로 값을 더해나가면 됩니다.

 

이렇게 하면 가중치를 넘기는 작업이 진행되며 이때 필요한 작업의 횟수는 넘겨주는(더하는) 값의 절댓값의 합입니다.

즉 2의 가중치의 노드에서 1의 가중치의 노드로 넘겨주면 1의 가중치의 노드는 1+2 = 3의 가중치의 노드가 됩니다.

이때 넘겨준 총량은 2이고 abs(2)가 필요한 작업의 횟수입니다.

 

절댓값을 취하는 이유는 만약 -3의 노드에서 1의 노드로 넘겨줄 때 필요한 횟수는 3이기 때문입니다.

 

이제 문제는 트리의 리프노드부터 시작하여 루트노드 까지 자신의 가중치를 부모노드에게 더하는 문제로 바뀌었습니다.

 

하지만, 분명 방금 전에 문제에서 제공하는 edges 데이터는 결과적으로 트리이긴 하지만 우리가 곧바로 트리로서 사용할 수 없다고 이야기했습니다. (그래프처럼 주어지기 때문)

그럼 이 그래프를 트리로 사용하려면 부모 자식 관계를 알아야 하고 루트를 알아야 합니다.

 

루트를 어떻게 구할까 고민을 많이 했었는데 사실..,, 이 문제에서는 정확한 루트를 구할 필요가 없었습니다.

➡️ 그래프에서 자신과 연결된 다른 노드의 개수가 1인 노드 중에서 아무거나 1개를 우리가 임의로 루트로 지정하면 됩니다.

실제로 위의 트리 그림은 입출력 예시 1번 그래프에서 2번 노드를 루트로 설정해서 그림을 그린 것입니다.

 

우리가 필요한건 리프 노드에서 로트 노드까지 가중치를 더해가는 과정이기 때문에 루트가 바뀌어도 동일한 결과 값이 나옵니다.

 

정리

• edges로 그래프 데이터 저장 (딕셔너리 활용하면 좋음!)
• 그래프에서 차수가 1인 정점 중에서 1개의 노드를 루트로 지정
• 해당 루트로 부터 자식 노드들을 dfs로 탐색하여 leaf 노드에 도달
• leaf 노드부터 부모 노드로 자신의 가중치를 더해감
• 이때 가중치의 절댓값을 별도의 변수 result에 더함
• 루트 노드에 도달하면 탐색 종료
• result를 리턴

 

 

풀이

1. Graph 구조체 구현

fileprivate struct Graph {
    var data = [Int: [Int]]()
    let count: Int
    
    init(count: Int) {
        self.count = count
        for i in 0..<count {
            data[i] = []
        }
    }
    
    mutating func insertEdge(with edge: [Int]) {
        data[edge[0]]!.append(edge[1])
        data[edge[1]]!.append(edge[0])
    }
    
    func findRoot() -> Int {
        for (key, value) in data {
            if value.count == 1 {
                return key
            }
        }
        
        return 0  // 여긴 실행 X
    }
}

딕셔너리를 활용해 그래프 데이터를 저장하는 구조체입니다.

findRoot 메서드는 차수가 1인 노드 중에서 1개를 루트로 지정하는 함수입니다.

 

2. solution 함수 구현

fileprivate func solution(_ a:[Int], _ edges:[[Int]]) -> Int64 {
    let sum = a.reduce(0, +)
    guard sum == 0 else { return -1 }
    
    var a = a
    
    var graph = Graph(count: a.count)
    
    for edge in edges {
        graph.insertEdge(with: edge)
    }
        
    var result = 0
    let root = graph.findRoot()
    var visited = Array(repeating: false, count: a.count)
    
    var parentDict = [Int: Int]() // key: 자식 노드, value: 부모 노드
    
    func dfs(cur: Int) {
        visited[cur] = true
        
        // leaf 노드까지 쭉 내려감
        if let children = graph.data[cur] {
            for child in children {
                if !visited[child] {    // 부모 노드를 재방문하는 것 방지
                    parentDict[child] = cur
                    dfs(cur: child)
                }
            }
        }

        if cur == root {
            // cur이 루트인 경우
            result += abs(a[cur])
            return
        }
        
        let parent = parentDict[cur]!
        
        a[parent] += a[cur]
        result += abs(a[cur])
    }

    dfs(cur: root)
    
    return Int64(result)
}

우선 모든 노드의 합이 0이 아니라면 -1을 리턴하고 시작합니다.

 

그래프를 생성하고 edge 데이터를 넣습니다.

한번 방문한 노드를 재방문 하는 것을 막기 위해 visited 배열을 만들었습니다. (dfs 탐색 중에 자식 노드에서 부모 노드로 탐색 보내는 것을 방지)

 

parentDict는 부모 자식 노드 관계를 저장합니다.

parentDict[3] = 2 라면 3의 부모 노드는 2라는 뜻입니다.

 

이것이 필요한 이유는 우리가 임의로 루트를 지정하여 트리를 구성했기 때문에 부모 자식 관계가 그래프에는 저장되어 있지 않습니다.

따라서 노드 A와 연결된 인접 노드들을 Graph로 부터 가져오고 이중에서 A의 부모가 아닌 것들만 Child로 파악해야 합니다.

따라서 부모 관계를 저장하는 딕셔너리가 필요했습니다.

 

dfs 함수를 보면 우선 children을 구하면서 트리의 아래쪽 리프 노드까지 쭉 내려가도록 했습니다.

리프 노드에 도달하면 이제 부모 노드에 자신의 가중치를 더해나갑니다.

result에는 abs(a[cur])을 더해주어 실행한 작업의 횟수를 기록합니다.

 

 

마무리

풀고나면 코드 자체는 간단하지만 아이디어를 떠올리는 것이 쉽지 않았습니다.

우선 주어진 edgs 자체가 곧바로 트리로 활용할 수 있었다면 훨씬 쉬웠겠지만 그렇지 않아서 루트를 임의로 지정한다는 발상이 필요했습니다.

 

리프 노드부터 부모 노드로 쭉 값을 더해 나가면 모든 노드가 예외 없이 0이 된다는 사실도 파악해야 했습니다.