Category: Kotlin coding test

In today’s lecture, we will explain the problem of calculating the area of a polygon. This problem is one of the frequently asked questions in coding tests, and we will learn how to implement an algorithm to calculate the area when given various shapes of polygons.

Problem Description

Write an algorithm to calculate the area of a polygon formed by given multiple points. The points are represented as coordinates on a 2D plane, and it is assumed that the points are given in either clockwise or counterclockwise order.

Example Input

    4
    0 0
    4 0
    4 3
    0 4
    

Example Output

    14.0
    

Here, the area is determined by the coordinates of the vertices that make up the polygon. In the above example, the given points are the vertices of a polygon consisting of (0,0), (4,0), (4,3), and (0,4). In this case, the area of the polygon is 14.0.

Algorithm Explanation

There are various methods to calculate the area of a polygon, but one commonly used method is the ‘Shoelace Formula’. Using this formula, the area can be calculated with a time complexity of O(n).

Shoelace Formula

The Shoelace Formula is expressed as follows:

A = 0.5 * | ∑(xiyi+1 - xi+1yi) |

Here, x_i and y_i are the x and y coordinates of the i-th vertex of the polygon. When the polygon has n vertices, i increments from 0 to n-1. The last vertex closes back to the first vertex (i.e., when increasing i+1, it wraps around to n).

Problem Solving Process

1. Processing Input Data

First, we need to read the number of vertices and the vertex coordinates of the polygon provided as input. In Kotlin, we can use a list to store the coordinates.

1. Problem Description

This problem is to find the shortest path between two nodes in a given graph. The graph is presented in the form of an adjacency list, providing the number of nodes and the information of nodes connected to each node. Your goal is to output the shortest path from a specific start node to a specific target node.

Problem

Input:
- First line: Number of vertices N (1 ≤ N ≤ 1000)
- Second line: Number of edges M (0 ≤ M ≤ 10000)
- Next M lines: Edge information (A B) - A and B represent the two connected nodes

- The last line gives the start node S and the target node T.

Output:
- Print the list of nodes in the path from S to T. If there is no path, print "PATH NOT FOUND!".

2. Problem Approach

This problem can be solved using a typical BFS algorithm. BFS is a breadth-first search method that explores nodes close to the start node first. This allows for finding the shortest path. The main characteristics of the BFS algorithm are as follows:

• It explores all nodes at the same depth, guaranteeing the shortest path.
• Implemented using a queue, it theoretically has a time complexity of O(V + E), where V is the number of nodes and E is the number of edges.

BFS Algorithm Steps

• Initialization: Mark the start node as visited and initialize distances. Insert the start node into the queue.
• Exploration Process: Repeat while the queue is not empty. Remove a node from the queue and add unvisited adjacent nodes to the queue.
• Path Tracking: Record the parent node of each node to allow for path tracking later.

3. Kotlin Code Implementation

Now, let’s implement BFS in Kotlin according to the approach above. Refer to the code below to see how to solve the given problem.

import java.util.*

data class Edge(val to: Int, val weight: Int)

fun bfs(graph: List>, start: Int, target: Int): List? {
    val queue: Queue = LinkedList()
    val visited = BooleanArray(graph.size)
    val parent = IntArray(graph.size) { -1 }  // Track parent nodes
    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val current = queue.poll()

        // Trace back the path if the target node is found
        if (current == target) {
            return tracePath(parent, start, target)
        }

        for (edge in graph[current]) {
            if (!visited[edge.to]) {
                visited[edge.to] = true
                parent[edge.to] = current // Set parent node
                queue.add(edge.to)
            }
        }
    }
    return null // No path found
}

fun tracePath(parent: IntArray, start: Int, target: Int): List {
    val path = mutableListOf()
    var current = target

    while (current != start) {
        path.add(current)
        current = parent[current]
    }
    path.add(start)
    path.reverse()  // Reverse the list as it was added in reverse order
    return path
}

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val m = scanner.nextInt()
    val graph = List(n) { mutableListOf() }

    // Create the graph
    for (i in 0 until m) {
        val a = scanner.nextInt() - 1
        val b = scanner.nextInt() - 1
        graph[a].add(Edge(b, 1)) // Undirected graph, so add both ways
        graph[b].add(Edge(a, 1))
    }

    val start = scanner.nextInt() - 1
    val target = scanner.nextInt() - 1
    val result = bfs(graph, start, target)

    if (result != null) {
        println(result.joinToString(" "))
    } else {
        println("PATH NOT FOUND!")
    }
}

4. Example Input and Output

Example 1

Input:
5 4
1 2
1 3
2 4
3 5
1 5

Output:
1 3 5

Example 2

Input:
5 3
1 2
2 3
4 5
1 4

Output:
PATH NOT FOUND!

5. Conclusion

In this tutorial, we addressed the problem of finding the shortest path between two nodes in a graph using breadth-first search (BFS). Due to the ease of exploration provided by BFS, it is widely useful in many algorithmic problems. It is essential to develop the ability to effectively utilize BFS to solve problems in actual exams or coding tests.

Now, we encourage you to tackle various problems using BFS. Enhance your understanding of algorithms through implementation in Kotlin, and develop the skills that can also be applied in real-world scenarios!