{"id":35178,"date":"2024-11-01T09:36:27","date_gmt":"2024-11-01T09:36:27","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35178"},"modified":"2024-11-01T11:44:45","modified_gmt":"2024-11-01T11:44:45","slug":"course-on-kotlin-coding-test-finding-cities-at-a-specific-distance","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35178\/","title":{"rendered":"Course on Kotlin Coding Test, Finding Cities at a Specific Distance"},"content":{"rendered":"

<\/p>\n

\n
\n

Written on:

\n

Introduction<\/h2>\n

\n Hello, in this Kotlin coding test tutorial, we will cover the algorithmic problem of ‘Finding Cities at a Specific Distance’.
\n This problem involves graph traversal and requires an algorithmic approach to find nodes in cities at a specific distance based on given conditions.
\n We will look at how to solve the problem step by step using Kotlin.\n <\/p>\n<\/section>\n

\n

Problem Description<\/h2>\n

\n The given graph consists of N cities and M bidirectional roads.
\n Each city is identified by numbers from 1 to N, and the roads connect two cities.
\n The goal is to find all cities that are exactly at the given distance K.\n <\/p>\n

\nInput Format<\/strong>
\n The first line contains the number of cities N (1 \u2264 N \u2264 30000) and the number of roads M (1 \u2264 M \u2264 200000), followed by the distance K (0 \u2264 K \u2264 30000) we want to find.
\n From the second line, M lines follow, each containing information about two connected cities A and B (1 \u2264 A, B \u2264 N).\n <\/p>\n

\nOutput Format<\/strong>
\n Output the numbers of cities that are exactly at distance K in ascending order; if there are no such cities, output -1.\n <\/p>\n<\/section>\n

\n

Problem Solving Approach<\/h2>\n

\n This problem involves exploring vertices in a graph that match the given conditions.
\n By using the BFS (Breadth-First Search) algorithm, we can find cities at a specific distance by searching to the appropriate depth.
\n BFS can be implemented using an empty queue and an adjacency list.\n <\/p>\n<\/section>\n

\n

Implementation Method<\/h2>\n

\n First, we construct an adjacency list based on the given city and road information.
\n Then we use the BFS algorithm to find the cities that reach the given distance K.\n <\/p>\n

The implementation steps are as follows:<\/p>\n

    \n
  1. Process input values: Read the number of cities, number of roads, and distance K.<\/li>\n
  2. Construct adjacency list: Store other cities connected to each city in list form.<\/li>\n
  3. Initialize BFS: Explore from the starting city to the distance K.<\/li>\n
  4. Store results: Save city numbers that have reached the distance K in a list.<\/li>\n
  5. Output results: Sort and print the cities reached at distance K.<\/li>\n<\/ol>\n<\/section>\n
    \n

    Code Implementation<\/h2>\n

    Below is the solution code implemented using the BFS algorithm in Kotlin:<\/p>\n

    \nimport java.util.*\n\nfun main() {\n    val scanner = Scanner(System.`in`)\n    val n = scanner.nextInt() \/\/ Number of cities\n    val m = scanner.nextInt() \/\/ Number of roads\n    val k = scanner.nextInt() \/\/ Desired distance\n    val x = scanner.nextInt() \/\/ Starting city\n\n    \/\/ Initialize adjacency list\n    val graph = Array(n + 1) { mutableListOf() }\n\n    \/\/ Input road information\n    for (i in 0 until m) {\n        val a = scanner.nextInt()\n        val b = scanner.nextInt()\n        graph[a].add(b)\n        graph[b].add(a)\n    }\n\n    \/\/ BFS implementation\n    val distance = IntArray(n + 1) { -1 }\n    distance[x] = 0\n    val queue: Queue = LinkedList()\n    queue.add(x)\n\n    while (queue.isNotEmpty()) {\n        val current = queue.poll()\n        for (neighbor in graph[current]) {\n            if (distance[neighbor] == -1) {\n                distance[neighbor] = distance[current] + 1\n                queue.add(neighbor)\n            }\n        }\n    }\n\n    \/\/ Find result cities\n    val result = mutableListOf()\n    for (i in 1..n) {\n        if (distance[i] == k) {\n            result.add(i)\n        }\n    }\n\n    \/\/ Output results\n    if (result.isEmpty()) {\n        println(-1)\n    } else {\n        result.sort()\n        for (city in result) {\n            println(city)\n        }\n    }\n}\n        <\/Int><\/Int><\/Int><\/code><\/pre>\n<\/section>\n
    \n
    Solution Analysis<\/h2>\n
    \n            The above code is a typical BFS implementation designed to solve the given problem.
    \n            In particular, by representing the road connectivity as an adjacency list, it optimizes memory usage and allows for fast searching.
    \n            BFS operates by exploring all nodes and placing adjacent nodes into a queue.
    \n            This way, it updates the distance to each node and ultimately collects nodes that stop at distance K.\n        <\/p>\n
    \n            If no city is found at distance K, returning -1 is also a good programming practice.
    \n            This code structure can be easily modified to suit different types of graph traversal problems.\n        <\/p>\n<\/section>\n
    \n
    Conclusion<\/h2>\n
    \n            Thus, we have learned about the process of implementing Kotlin code using the BFS algorithm to solve the ‘Finding Cities at a Specific Distance’ problem.
    \n            This problem helps in understanding the basics of graph problems and can develop problem-solving skills for various problem types.
    \n            It will also be beneficial for effectively applying algorithms in work or personal projects.
    \n            We plan to cover more diverse algorithm problems in the future, so please stay tuned.\n        <\/p>\n<\/section>\n