Journey to the Moon

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

문제

같은 국적을 가진 우주비행사 정보가 쌍으로 주어질 때, 다른 국적을 가진 2명의 비행사를 선발할 수 있는 경우의 수를 반환하라.

1. 나의 풀이

해당 문제는 graph 내에 존재하는 컴포넌트들의 조합을 구하여 반환하는 문제이다. 간단하게 dfs로 컴포넌트를 찾고 계산해주었다.

function dfs(graph, start, visited) {
    const stack = [start]
    visited[start] = true;

    let count = 1;
    while(stack.length) {
        const current = stack.pop();
        
        for (const next of graph[current]) {
            if (!visited[next]) {
                count++;
                stack.push(next);
                visited[next] = true;
            }
        }
    }
    
    return count;
}

function journeyToMoon(n, astronaut) {
    // Write your code here
    const graph = Array.from(new Array(n), () => []);
    const visited = Array.from(new Array(n), () => false);
    
    astronaut.forEach(([n1, n2]) => {
        graph[n1].push(n2);
        graph[n2].push(n1);
    });
    
    const counts = [];
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            counts.push(
              dfs(graph, i, visited)
            );
        }
    }

    let total = 0;
    while (counts.length) {
        const cc = counts.pop();
        for (const c of counts) {
            total += (cc * c);
        }
    }

    return total;
}

2. 다른사람의 풀이

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