[Kotlin] Korean Coding Test - Programmers - Kakao Friends Coloring Book

Question

Link

Apeach, the publisher's editor, asked Neo to draw the original for the coloring book and received several paintings. Appeach, who wanted to put several pictures in the coloring book in order of difficulty, found that it would be difficult to color if there were many areas, and defined the difficulty of the picture as the number of areas. (Area means spaces of the same color connected up, down, left and right.)

Let's write a program to calculate how many areas there are in the figure and what the area of the largest area is.

Restrictions

The input is given by a two-dimensional array picture of m and n representing the size of the figure, and m × n representing the figure. The restrictions are as follows.

• 1 <= m, n <= 100
• The element in the picture is any value between 0 and 2^31-1.
• A value of 0 among the elements of picture means an area not colored.

A return type is an integer array of two elements. Returns how many areas are in the figure and how many spaces are in the largest area.

Input/Output example

Input

• m: 6
• n: 4
• picture

Output: [4, 5]

Solve

Since it is a problem of obtaining a coloring area, zero, which is a colorless area, is excluded.

A graph search algorithm is used to determine how far the same color is connected.

Arrays are used together to prevent duplicate checks.

Code. Kotlin

class Solution {
    // Up, down, left, right coordinates
    private val distanceX = intArrayOf(0, 0, -1, 1)
    private val distanceY = intArrayOf(-1, 1, 0, 0)
    // Visit or not
    private lateinit var visited: Array<BooleanArray>
    private var count = 0

    private fun solution(m: Int, n: Int, picture: Array<IntArray>): IntArray {
        visited = Array(m) { BooleanArray(n) { false } }

        val color = mutableListOf<Int>()

        for (y in 0 until m) {
            for (x in 0 until n) {
                if (picture[y][x] == 0 || visited[y][x]) continue
                dfs(n, m, x, y, picture[y][x], picture)
                color.add(count)
                count = 0
            }
        }

        color.sort()
        return intArrayOf(color.size, color.last())
    }

    private fun dfs(n: Int, m: Int, x: Int, y: Int, target: Int, picture: Array<IntArray>) {
        visited[y][x] = true
        count++

        for (i in 0..3) {
            val nextY = y + distanceY[i]
            val nextX = x + distanceX[i]

            if (nextY >= m || nextX >= n || nextY < 0 || nextX < 0) continue
            if (visited[nextY][nextX] || picture[nextY][nextX] == 0) continue
            if (target != picture[nextY][nextX]) continue

            dfs(n, m, nextX, nextY, target, picture)
        }
    }
}

No Kotlin submissions. Example I/O Passes

Code. JAVA

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    private int[] distanceX = {0, 0, -1, 1};
    private int[] distanceY = {-1, 1, 0, 0};

    private boolean[][] visited;
    private int count = 0;
    
    public int[] solution(int m, int n, int[][] picture) {
        visited = new boolean[m][n];

        List<Integer> color = new ArrayList<>();

        for (int y = 0; y < m; y++) {
            for (int x = 0; x < n; x++) {
                if (picture[y][x] == 0 || visited[y][x]) continue;
                dfs(n, m, x, y, picture[y][x], picture);
                color.add(count);
                count = 0;
            }
        }

        Collections.sort(color, Collections.reverseOrder());
        return new int[]{color.size(), color.get(0)};
    }

    private void dfs(int n, int m, int x, int y, int target, int[][] picture) {
        visited[y][x] = true;
        count++;

        for (int i = 0; i < 4; i++) {
            int nextY = y + distanceY[i];
            int nextX = x + distanceX[i];

            if (nextY >= m || nextX >= n || nextY < 0 || nextX < 0) continue;
            if (visited[nextY][nextX] || picture[nextY][nextX] == 0) continue;
            if (target != picture[nextY][nextX]) continue;

            dfs(n, m, nextX, nextY, target, picture);
        }
    }
}

TEST 1 〉	Pass (15.27ms, 94.5MB)

Kotlin Full Code Link