자바스크립트 코딩테스트 강좌, 빌딩 순서 구하기

본 글에서는 자바스크립트 코딩테스트 문제 중에서 ‘빌딩 순서 구하기’ 문제를 다룰 것입니다. 이 문제는 그래프 이론과 위상 정렬(topological sorting) 개념을 활용하여 풀 수 있는 흥미로운 문제입니다. 시작하기 전에 문제의 정의와 요구사항을 살펴보겠습니다.

문제 정의

주어진 N개의 빌딩과 그들 사이의 의존 관계를 바탕으로, 모든 빌딩을 건설하기 위해 필요한 순서를 구하는 문제입니다. 빌딩 A가 빌딩 B보다 먼저 건설되어야 한다면, 이 두 빌딩 사이에는 의존 관계가 있다고 할 수 있습니다.

입력


입력은 다음과 같은 형식이다:
- 첫 줄: N (빌딩의 개수), M (의존 관계의 수)
- 다음 M줄: A B (빌딩 A는 빌딩 B보다 먼저 건설되어야 함을 나타냄)

출력


가능한 빌딩 건설 순서를 한 줄에 공백으로 구분하여 출력한다. 단, 순서가 가능하지 않을 경우 "Impossible"을 출력한다.

예제

예제 1


입력:
4 2
1 2
2 3

출력:
1 2 3 4

예제 2


입력:
3 3
1 2
2 3
3 1

출력:
Impossible

문제 해결 과정

위상 정렬(Topological Sorting)

이 문제의 해결에 있어서 가장 중요한 개념은 위상 정렬입니다. 위상 정렬은 방향성이 있는 그래프에서 모든 정점의 선후 관계를 고려하여 정렬된 형태로 나열하는 방법입니다. 위상 정렬의 결과가 존재하려면 그래프가 사이클이 없어야 합니다. 즉, 모든 의존 관계가 명확해야만 순서를 정할 수 있습니다.

문제 해결 알고리즘

문제를 해결하기 위한 알고리즘을 다음과 같이 구성할 수 있습니다.

그래프의 정점 수(N)와 간선 수(M)를 읽습니다.
그래프의 인접 리스트를 생성하면서, 각 빌딩이 건설되기 위해 필요한 빌딩의 수(진입 차수)를 카운트합니다.
진입 차수가 0인 빌딩을 큐에 추가합니다.
큐에서 빌딩을 하나씩 꺼내어 결과 리스트에 추가하고, 그 빌딩과 의존 관계에 있는 빌딩들의 진입 차수를 감소시킵니다.
진입 차수가 0이 되는 빌딩을 큐에 추가합니다.
모든 빌딩을 처리한 후, 결과 리스트의 길이가 N과 같으면 가능한 건설 순서를 출력하고, 그렇지 않으면 “Impossible”을 출력합니다.

자바스크립트 코드 구현


function getConstructionOrder(N, M, dependencies) {
    const graph = Array.from({ length: N + 1 }, () => []);
    const indegree = Array.from({ length: N + 1 }, () => 0);
    
    // 의존 관계를 그래프에 추가
    for (const [a, b] of dependencies) {
        graph[a].push(b);
        indegree[b]++;
    }
    
    const queue = [];
    
    // 진입 차수가 0인 노드 추가
    for (let i = 1; i <= N; i++) {
        if (indegree[i] === 0) {
            queue.push(i);
        }
    }
    
    const order = [];
    
    while (queue.length > 0) {
        const current = queue.shift();
        order.push(current);
        
        for (const neighbor of graph[current]) {
            indegree[neighbor]--;
            if (indegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

    return order.length === N ? order : "Impossible";
}

// 테스트 예제
const N = 4;
const M = 2;
const dependencies = [[1, 2], [2, 3]];
const result = getConstructionOrder(N, M, dependencies);
console.log(result.join(' ')); // 출력: 1 2 3 4

결론

이번 강좌에서는 ‘빌딩 순서 구하기’ 문제를 통해 위상 정렬의 개념과 자바스크립트로 문제를 해결하는 방법을 배웠습니다. 임의의 입력에 대해 그래프를 구성하고, 이 그래프를 기반으로 가능한 건설 순서를 도출하는 과정을 통해 알고리즘 문제 해결 능력을 향상시킬 수 있기를 바랍니다. 다양한 테크니컬 인터뷰에서 유사한 문제가 출제될 수 있으므로, 지속적인 연습과 이해가 필요합니다. 감사합니다!

참고 자료

관련된 자료와 알고리즘에 대한 이해를 더 깊이 있게 하고 싶다면 아래의 자료를 참고하세요.