C# Coding Test Course, Finding Cities at a Specific Distance

Hello everyone. Today, we will learn how to solve the “Finding Cities at a Specific Distance” problem using C#. This problem often appears in coding tests and utilizes graph and BFS (Breadth-First Search) algorithms. Therefore, this course will be a great help in enhancing your understanding of graph theory and algorithms.

Problem Description

Let me introduce a problem based on given conditions.

Problem:

There are N cities and M bidirectional roads. Each city is numbered from 1 to N. When there is a road connecting two cities A and B, the length of the road connecting A and B is always considered as 1. Given a specific city X and distance K, you need to output all cities that are exactly at distance K.

Input Format:
The first line contains the number of cities N, the number of roads M, distance K, and starting city X.
Following that, M lines will contain the two cities connected by each road.

Output Format:
Output the numbers of the cities at distance K in ascending order.
If there are no such cities, output -1.

Input Example

4 4 2 1
1 2
1 3
2 3
2 4

Output Example

4

Problem Analysis

To solve this problem, we need a method to represent and search the graph.
Each city can be represented as a vertex, and roads as edges.
We need to find a specific distance using BFS or DFS algorithms.
In this case, we are looking for distance K, so BFS is more suitable because it explores from the closest nodes, thus naturally applying the concept of distance.

Problem Solving Process

Step 1: Define Data Structures

First, we will use lists and a queue to represent cities and roads.
– The list will store the roads connected to each city.
– The queue is the data structure necessary for performing BFS.

Step 2: Create the Graph

We will take city and road information as input to create an adjacency list.
To use the data starting from index 1, we will set the size to N + 1.

Step 3: Implement BFS

We will implement the BFS function starting from the departure city X.
We will find cities at distance K and store the results.

Step 4: Output Results

Sort the result list and output it.
If there are no cities at distance K, output -1.

C# Code Implementation

Here is the C# code to solve the given problem.

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    static List[] graph;
    static bool[] visited;
    static List result;
    
    public static void Main(string[] args)
    {
        // Input
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]); // Number of cities
        int M = int.Parse(input[1]); // Number of roads
        int K = int.Parse(input[2]); // Distance
        int X = int.Parse(input[3]); // Starting city
        
        // Initialize graph
        graph = new List[N + 1];
        for (int i = 1; i <= N; i++)
        {
            graph[i] = new List();
        }
        
        // Input road information
        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            graph[a].Add(b);
            graph[b].Add(a);
        }
        
        // BFS and result generation
        visited = new bool[N + 1];
        result = new List();
        BFS(X, 0, K);
        
        // Output results
        result.Sort();
        if (result.Count == 0)
        {
            Console.WriteLine(-1);
        }
        else
        {
            foreach (int city in result)
            {
                Console.WriteLine(city);
            }
        }
    }
    
    static void BFS(int start, int distance, int K)
    {
        Queue> queue = new Queue>();
        queue.Enqueue(new Tuple(start, distance));
        visited[start] = true;
        
        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            int currentCity = current.Item1;
            int currentDistance = current.Item2;
            
            // If a city at distance K is found
            if (currentDistance == K)
            {
                result.Add(currentCity);
                continue;
            }
            
            // Explore adjacent cities
            foreach (var neighbor in graph[currentCity])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(new Tuple(neighbor, currentDistance + 1));
                }
            }
        }
    }
}

Code Explanation

I will briefly explain the process of solving the problem through the C# code above.

• Data Input: Read the values for the number of cities, number of roads, distance K, and starting city X from the first line, and input M road information.
• Graph Construction: Construct an adjacency list to represent cities as vertices and roads as edges.
• BFS Algorithm Implementation: Use a Queue to execute BFS and calculate the distance to each city.
• Output Results: Return the sorted results, and if there are no cities matching distance K, output -1.

Conclusion

In this lecture, we learned how to solve the “Finding Cities at a Specific Distance” problem using C#.
I hope you felt the importance of graph data structures and search algorithms through the distance-based exploration process using BFS.
In the next lecture, we will solve even more diverse problems together.