JavaScript Coding Test Course, Find Cities at a Specific Distance

Hello, everyone! Today we will discuss an algorithm problem to find cities at a specific distance using JavaScript. This problem is one of the frequently featured topics in coding tests, where you will learn how to apply graph traversal and BFS (Breadth-First Search) techniques.

Problem Description

Write a function that returns a list of cities located at a specific distance starting from the given two vertices. The cities are connected by edges, and it is assumed that the distance calculation for each edge is equal to 1.

Input

  • n: the number of cities (1 ≤ n ≤ 300,000)
  • edges: the edges connecting each city, given as a 2D array. edges[i] = [a, b] means city a is directly connected to city b.
  • start: the city from which the distance calculation will start (1 ≤ start ≤ n)
  • distance: a specific distance k (0 ≤ distance ≤ n)

Output

Return an array of cities that are at a specific distance, sorted in ascending order. If there are no such cities, return an empty array.

Problem Solving Strategy

The key to this problem is exploring the graph using the BFS algorithm. BFS is a technique that can explore all vertices in a graph and is suitable for finding the shortest path.

The basic steps to solve the problem are as follows:

  1. Define the graph structure using the given edges array.
  2. Calculate the distance from the given start city to each city using BFS.
  3. Collect the cities whose distance matches the specific distance.
  4. Sort the resulting city list in ascending order and return it.

Implementation Steps

Step 1: Graph Structuring

We will use an adjacency list to hold the connection information between cities. This will be composed of an object where each city is the key and the list of connected cities is the value.

Step 2: Implementing BFS Algorithm

Using BFS, we will calculate the distance from the starting city to each city and find the cities that can be reached at a specific distance.

Step 3: Processing and Returning Results

Collect the cities that match the specific distance, sort them, and return the result.

JavaScript Code Implementation


function findCitiesAtDistance(n, edges, start, distance) {
    // Step 1: Create the graph
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a); // Add to both sides for a bidirectional graph
    }
    
    // Step 2: Set variables for BFS
    const queue = [];
    const distances = Array(n + 1).fill(-1); // Initialize distances
    distances[start] = 0;
    queue.push(start);
    
    // Perform BFS traversal
    while (queue.length > 0) {
        const currentCity = queue.shift();
        
        for (const neighbor of graph[currentCity]) {
            // If the city has not been visited
            if (distances[neighbor] === -1) {
                distances[neighbor] = distances[currentCity] + 1;
                queue.push(neighbor);
            }
        }
    }
    
    // Step 3: Find cities at a specific distance
    const result = [];
    for (let city = 1; city <= n; city++) {
        if (distances[city] === distance) {
            result.push(city);
        }
    }

    // Sort in ascending order
    result.sort((a, b) => a - b);
    return result;
}

Code Explanation

The code above is a function that finds cities at a specific distance according to the given requirements. I will explain each step:

Graph Creation

We create the graph structure by iterating through the edges array and storing the connection information between each city. An adjacency list is used to keep the list of cities connected to each city.

BFS Implementation

This is the process of calculating distance values using BFS from the starting city. We use a distances array to record the distances of each city, marking visited cities as -1 to prevent duplication.

Result Processing

After exploring all the cities, we add the cities that match the specific distance to the result list and finally sort them in ascending order before returning.

Test Cases

Now let’s check the operation of the implemented code through some test cases.


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

Conclusion

In this post, we covered an algorithm problem to find cities at a specific distance and explained the basic principles of graph traversal using BFS. Through this problem, we learned various concepts such as graph structuring, BFS implementation, and result processing. Since such problems are frequently presented in coding tests, understanding and practicing them is important. Next time, we will tackle more complex graph problems. Thank you!