*Cut the Tree

사이트: HackerRank
난이도: 미디움
분류: Search

문제

각 노드마다 값이 존재하는 트리가 주어질 때, 해당 트리의 값은 전체 노드 값들의 합이 된다. 이 때 특정 간선을 잘라 2개의 트리를 만들었을 때, 각 트리의 값의 차이가 가장 적은 값을 반환하라.

1. 나의 풀이

해당 문제는 tree이지만 graph로 해결하는 것이 편하다. 처음에 tree라는 단어에 꽂혀서 tree 자료 구조대로 구현했는데, 애매한 부분이 많아서 graph로 변경하여 풀어보았다.
다만 recursive dfs를 사용해야 편한 알고리즘인데 입력 값의 수가 100,000 개 까지라서 runtime error를 계속 내뱉는 상황이 발생하였다. 몇 가지 시도를 해보다가 시간이 너무 지체되어 추후에 stack dfs의 반환값을 처리하는 로직을 고민하기로 했다.

function dfs(graph, data, index, visited) {
    let sum = 0;

    for (const node of graph[index]) {
        if (!visited[node]) {
            visited[node] = data[node - 1];
            sum += dfs(graph, data, node, visited);
        }
    }

    return visited[index] += sum;
}

function cutTheTree(data, edges) {
    // Write your code here
    const graph = Array.from(new Array(data.length + 1), () => []);
    const visited = new Array(data.length + 1).fill(0);
    visited[1] = data[0];
    
    edges.forEach(([node1, node2], index) => {
        graph[node1].push(node2);
        graph[node2].push(node1);
    });
    
    const total = dfs(graph, data, 1, visited);
    let min = total;

    for (let i = 2; i < visited.length; i++) {
        const other = total - visited[i];
        const sub = Math.abs(visited[i] - other);
        
        if (min > sub) {
            min = sub;
        }
    }

    return min;
}

위 로직은 다른 언어들이라면 잘 해결될 것이나, javascript는 그렇지 않다.

function dfs(graph, data, visited) {
    // const visited = new Array(data.length + 1).fill(0);
    const stack = [[1, null]];
    const stack2 = [];
    
    // visited[1] = data[0];
    
    while(stack.length) {
        console.log('stack:', stack);
        const [index, parent] = stack.pop();
        stack2.push([index, parent]);
        
        for (const node of graph[index]) {
            if (!visited[node]) {
                visited[node] = data[node - 1];
                stack.push([node, index]);
            }
        }
    }
    
    while(stack2.length) {
        const [index, parent] = stack2.pop(); 
        if (parent !== null) {
            visited[parent] += visited[index];
        }
    }
    
    return visited[1];
}

위와 같이 반환값의 처리를 하기위해 루프를 두번 돌리는 시도를 해봤는데, Timeout 과 Runtiem error를 내뱉는 테스트케이스들이 있어서 일단은 넘어가기로 했다.

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.