자바스크립트 코딩테스트 강좌, 특정 거리의 도시 찾기

안녕하세요, 여러분! 오늘은 자바스크립트를 사용하여 특정 거리에 있는 도시를 찾는 알고리즘 문제에 대해 다루어보겠습니다. 이 문제는 코딩 테스트에서 자주 출제되는 주제 중 하나로, 그래프 탐색 및 BFS(너비 우선 탐색) 기법을 응용하는 방법을 배우게 될 것입니다.

문제 설명

주어진 두 정점으로부터 시작하여 특정 거리만큼 떨어진 도시들의 리스트를 반환하는 함수를 작성하세요. 도시는 간선으로 연결되어 있으며, 거리 계산은 각 간선이 1로 동일하다고 가정합니다.

입력

n: 도시의 개수 (1 ≤ n ≤ 300,000)
edges: 각 도시를 연결하는 간선들, 이것은 2차원 배열로 주어집니다. edges[i] = [a, b]는 도시 a와 도시 b가 직접 연결되어 있다는 것을 의미합니다.
start: 평균적으로 거리 계산을 시작할 도시 (1 ≤ start ≤ n)
distance: 특정 거리 k (0 ≤ distance ≤ n)

출력

특정 거리만큼 떨어진 도시들의 배열을 오름차순으로 정렬하여 반환하십시오. 만약 그러한 도리가 없다면 빈 배열을 반환합니다.

문제 해결 전략

이 문제의 핵심은 BFS 알고리즘을 이용하여 그래프를 탐색하는 것입니다. BFS는 그래프의 모든 정점을 탐색할 수 있는 기법으로, 최단 경로를 찾는 데 적합합니다.

문제를 해결하기 위한 기본 단계는 다음과 같습니다:

주어진 edges 배열을 통해 그래프 구조를 정의합니다.
BFS를 통해 주어진 start 도시에서 각 도시까지의 거리를 계산합니다.
거리 값이 특정 거리와 일치하는 도시들을 수집합니다.
결과 도시 리스트를 오름차순으로 정렬하여 반환합니다.

구현 단계

1단계: 그래프 구조화

도시와 도시 간의 연결 정보를 담기 위해 인접 리스트를 사용할 것입니다. 이는 각 도시를 키로 하고 연결된 도시의 리스트를 값으로 갖는 객체로 구성됩니다.

2단계: BFS 알고리즘 구현

BFS를 통해 시작 도시로부터 각 도시까지의 거리를 계산하고, 특정 거리에 도달할 수 있는 도시를 찾아냅니다.

3단계: 결과 처리 및 반환

특정 거리와 일치하는 도시들을 수집하여 정렬한 후 반환합니다.

자바스크립트 코드 구현


function findCitiesAtDistance(n, edges, start, distance) {
    // Step 1: 그래프 생성
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a); // 양방향 그래프이므로 양쪽 모두 추가
    }
    
    // Step 2: BFS를 위한 변수 설정
    const queue = [];
    const distances = Array(n + 1).fill(-1); // 거리 초기화
    distances[start] = 0;
    queue.push(start);
    
    // BFS 탐색 수행
    while (queue.length > 0) {
        const currentCity = queue.shift();
        
        for (const neighbor of graph[currentCity]) {
            // 아직 방문하지 않은 도시인 경우
            if (distances[neighbor] === -1) {
                distances[neighbor] = distances[currentCity] + 1;
                queue.push(neighbor);
            }
        }
    }
    
    // Step 3: 특정 거리에 있는 도시 찾기
    const result = [];
    for (let city = 1; city <= n; city++) {
        if (distances[city] === distance) {
            result.push(city);
        }
    }

    // 오름차순으로 정렬
    result.sort((a, b) => a - b);
    return result;
}

코드 설명

위의 코드는 주어진 요구사항에 맞춰 특정 거리의 도시를 찾는 함수입니다. 각 단계에 대해 설명하겠습니다:

그래프 생성

edges 배열을 순회하며, 각 도시 간의 연결 정보를 그래프 구조로 만들었습니다. 이때, 인접 리스트를 사용하여 각 도시가 연결된 도시 리스트를 보관합니다.

BFS 구현

BFS를 사용하여 시작 도시로부터의 거리 값을 계산하는 과정입니다. 각 도시의 거리를 기록하기 위해 distances 배열을 사용하며, 방문한 도시는 -1로 표시하여 중복 처리를 방지합니다.

결과 처리

모든 도시를 탐색한 후, 특정 거리와 일치하는 도시를 결과 리스트에 추가하고, 최종적으로 오름차순으로 정렬한 후 반환합니다.

테스트 케이스

이제 몇 가지 테스트 케이스를 통해 구현된 코드의 동작을 확인해 보겠습니다.


console.log(findCitiesAtDistance(6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4]], 5, 2)); 
// 출력: [4, 5, 6]
console.log(findCitiesAtDistance(4, [[1, 2], [1, 3], [2, 4]], 1, 2)); 
// 출력: [4]
console.log(findCitiesAtDistance(5, [[1, 2], [1, 3], [1, 4], [2, 5]], 1, 1)); 
// 출력: [2, 3, 4]
console.log(findCitiesAtDistance(7, [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7]], 1, 3)); 
// 출력: [4]
console.log(findCitiesAtDistance(3, [], 1, 1)); 
// 출력: []

결론

이번 글에서는 특정 거리의 도시를 찾는 알고리즘 문제를 다루며, BFS를 활용한 그래프 탐색의 기본 원리를 설명했습니다. 이 문제를 통해 그래프 구조화, BFS 구현, 결과 처리 등 여러가지를 배울 수 있었습니다. 이러한 문제는 코딩 테스트에서 자주 출제되므로 이해하고 연습하는 것이 중요합니다. 다음 시간에는 더 복잡한 그래프 문제를 다루도록 하겠습니다. 감사합니다!