*The Story of a Tree

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

문제

방향이 없는 간선 정보가 주어지고 n개의 노드가 주어진다고 했을 때, 각 노드(1 ~ n)가 root인 트리에서 부모-자식 관계를 예측하려고 한다. 주어진 예측 정보를 가지고 특정 노드가 root가 되었을 때 예측 정보가 모두 맞는 경우의 수를 찾아서 반환하라. 이 때, 반환값은 예측이 모두 맞은 경우의 수 / 노드 수가 된다.

반환 값이 최대 공약수 적용이 가능할 경우, 최적화 후 반환한다.

1. 나의 풀이

일단은 각 root마다 dfs를 호출하는 바람에 time limited 오류가 발생했다. 해당 문제는 추후에 좀 더 개선해보겠다.

function dfs(start, graph, guessFails) {
    const stack = [start];
    const visited = new Set([start]);
    
    while(stack.length) {
        const current = stack.pop();
        
        for (const next of graph[current]) {
            if (!visited.has(next)) {
                if (guessFails[next] && guessFails[next].has(current)) {
                    return false;
                }
                visited.add(next);
                stack.push(next);
            }
        }
    }
    
    return true;
}

function gcd(a, b) {
    if (b > 0) {
        return gcd(b, a % b);
    }
    return a;
}

function storyOfATree(n, edges, k, guesses) {
    // Write your code here
    const graph = Array.from(new Array(n + 1), () => []);
    edges.forEach(([u, v]) => {
        graph[u].push(v);
        graph[v].push(u);
    });
    
    const guessFails = guesses.reduce((ret, [u, v]) => {
        if (!ret[u]) {
            ret[u] = new Set();
        }
        ret[u].add(v);
        return ret;
    }, {});
    let count = 0;
    
    for (let i = 1; i <= n; i++) {
        if (dfs(i, graph, guessFails)) {
            count++;
        }
    }

    const g = gcd(count, n);
    return `${count / g}/${n / g}`;
}

2. 다른사람의 풀이

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