{"id":33938,"date":"2024-11-01T09:22:12","date_gmt":"2024-11-01T09:22:12","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33938"},"modified":"2024-11-01T10:54:58","modified_gmt":"2024-11-01T10:54:58","slug":"c-coding-test-course-finding-cities-at-a-specific-distance","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33938\/","title":{"rendered":"C# Coding Test Course, Finding Cities at a Specific Distance"},"content":{"rendered":"

<\/p>\n

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.<\/p>\n

Problem Description<\/h2>\n

\n Let me introduce a problem based on given conditions. <\/p>\n

Problem<\/strong>:

\n 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. <\/p>\n

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

Output Format<\/strong>:
\n Output the numbers of the cities at distance K in ascending order.
\n If there are no such cities, output -1.\n<\/p>\n

Input Example<\/h3>\n
\n4 4 2 1\n1 2\n1 3\n2 3\n2 4\n<\/pre>\n
Output Example<\/h3>\n
\n4\n<\/pre>\n
Problem Analysis<\/h2>\n
\n    To solve this problem, we need a method to represent and search the graph.
\n    Each city can be represented as a vertex, and roads as edges.
\n    We need to find a specific distance using BFS or DFS algorithms.
\n    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.\n<\/p>\n
Problem Solving Process<\/h2>\n
Step 1: Define Data Structures<\/h3>\n
\n    First, we will use lists and a queue to represent cities and roads.
\n    – The list will store the roads connected to each city.
\n    – The queue is the data structure necessary for performing BFS.\n<\/p>\n
Step 2: Create the Graph<\/h3>\n
\n    We will take city and road information as input to create an adjacency list.
\n    To use the data starting from index 1, we will set the size to N + 1.\n<\/p>\n
Step 3: Implement BFS<\/h3>\n
\n    We will implement the BFS function starting from the departure city X.
\n    We will find cities at distance K and store the results.\n<\/p>\n
Step 4: Output Results<\/h3>\n
\n    Sort the result list and output it.
\n    If there are no cities at distance K, output -1.\n<\/p>\n
C# Code Implementation<\/h2>\n
Here is the C# code to solve the given problem.<\/p>\n
\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\n\npublic class Program\n{\n    static List[] graph;\n    static bool[] visited;\n    static List result;\n    \n    public static void Main(string[] args)\n    {\n        \/\/ Input\n        string[] input = Console.ReadLine().Split(' ');\n        int N = int.Parse(input[0]); \/\/ Number of cities\n        int M = int.Parse(input[1]); \/\/ Number of roads\n        int K = int.Parse(input[2]); \/\/ Distance\n        int X = int.Parse(input[3]); \/\/ Starting city\n        \n        \/\/ Initialize graph\n        graph = new List[N + 1];\n        for (int i = 1; i <= N; i++)\n        {\n            graph[i] = new List();\n        }\n        \n        \/\/ Input road information\n        for (int i = 0; i < M; i++)\n        {\n            input = Console.ReadLine().Split(' ');\n            int a = int.Parse(input[0]);\n            int b = int.Parse(input[1]);\n            graph[a].Add(b);\n            graph[b].Add(a);\n        }\n        \n        \/\/ BFS and result generation\n        visited = new bool[N + 1];\n        result = new List();\n        BFS(X, 0, K);\n        \n        \/\/ Output results\n        result.Sort();\n        if (result.Count == 0)\n        {\n            Console.WriteLine(-1);\n        }\n        else\n        {\n            foreach (int city in result)\n            {\n                Console.WriteLine(city);\n            }\n        }\n    }\n    \n    static void BFS(int start, int distance, int K)\n    {\n        Queue> queue = new Queue>();\n        queue.Enqueue(new Tuple(start, distance));\n        visited[start] = true;\n        \n        while (queue.Count > 0)\n        {\n            var current = queue.Dequeue();\n            int currentCity = current.Item1;\n            int currentDistance = current.Item2;\n            \n            \/\/ If a city at distance K is found\n            if (currentDistance == K)\n            {\n                result.Add(currentCity);\n                continue;\n            }\n            \n            \/\/ Explore adjacent cities\n            foreach (var neighbor in graph[currentCity])\n            {\n                if (!visited[neighbor])\n                {\n                    visited[neighbor] = true;\n                    queue.Enqueue(new Tuple(neighbor, currentDistance + 1));\n                }\n            }\n        }\n    }\n}\n<\/pre>\n
Code Explanation<\/h2>\n
\n    I will briefly explain the process of solving the problem through the C# code above.\n<\/p>\n