🔗 Kakao Friends Coloring Book

Apeach, an editor at a publishing house, asked Neo to draw original artwork for a coloring book and received several pictures. Wanting to arrange the pictures in the coloring book in order of difficulty, Apeach discovered that having more regions makes coloring more tricky and difficult, and so defined the difficulty of a picture as the number of regions. (A region refers to a space of the same color connected up, down, left, and right.)

Let's write a program that calculates how many regions are in a picture and how large the largest region is.

The picture above consists of a total of 12 regions, and the largest region is Apeach's face, with an area of 120.

The input is given as m and n, representing the picture's dimensions, and a 2-dimensional array picture of size m × n representing the picture. The constraints are as follows.

• 1 <= m, n <= 100
• The elements of picture are arbitrary values from 0 to 2^31 - 1, inclusive.
• An element of picture with a value of 0 represents a region that is not colored in.

The return type is an integer array with two elements. It returns how many regions are in the picture and how many cells make up the largest region.

The picture given as an example consists of a total of 4 regions. The region at the top left and the region on the right are both made up of 1s, but since they aren't connected up, down, left, or right, they count as different regions. The largest region is the top-left region occupied by 1s, with a total of 5 cells.

We're given a picture in which the picture is divided into regions, with colors represented as numbers. We need to calculate the number of regions where adjacent cells share the same color, and the size of the largest of these regions.

For problems like this, involving finding adjacent connected regions, applying the BFS algorithm works well.

BFS algorithm is also known as breadth-first search.

• Search centered on breadth
• Favors nodes with shallower depth
• Implemented using a Queue

As we scan through each element of picture, whenever we find a region with a valid color, we search the adjacent region using the BFS algorithm.

1. Put region 1, which has a color, into the queue and mark it as visited. Then remove it from the queue.
2. Based on region 1, search for regions at a distance of 1. Put 2 into the queue.
3. Likewise, put region 4, which is at a distance of 1, into the queue.
4. Examine the most recently entered region, 2. Mark it as visited and remove it from the queue.
5. Examine region 4. Mark it as visited and remove it from the queue. During the search, insert the adjacent region 7 into the queue.
6. Examine region 7. Mark it as visited and remove it from the queue.

In this way, the search proceeds sequentially according to distance.

JAVA
import java.util.LinkedList;
import java.util.Queue;

/**
 * Kakao Friends Coloring Book class
 *
 * @author RWB
 * @since 2021.12.25 Sat 13:52:12
 */
class Solution
{
	private static final int[] DX = { 0, 0, -1, 1 };
	private static final int[] DY = { -1, 1, 0, 0 };
	
	private boolean[][] isVisit;
	
	/**
	 * Method that returns the answer
	 *
	 * @param m: [int] height of the picture
	 * @param n: [int] length of the picture
	 * @param picture: [int[][]] original picture artwork
	 *
	 * @return [int[]] answer
	 */
	public int[] solution(int m, int n, int[][] picture)
	{
		int[] answer = { 0, 0 };
		
		// Modifying picture directly causes an error in the problem
		int[][] copy = picture.clone();
		
		isVisit = new boolean[m][n];
		
		for (int i = 0; i < copy.length; i++)
		{
			for (int j = 0; j < copy[i].length; j++)
			{
				// If the artwork has a valid color and hasn't been visited yet
				if (copy[i][j] > 0 && !isVisit[i][j])
				{
					answer[0]++;
					answer[1] = Math.max(answer[1], bfs(m, n, i, j, copy));
				}
			}
		}
		
		return answer;
	}
	
	/**
	 * Method that returns the result of the breadth-first search algorithm
	 *
	 * @param m: [int] height of the picture
	 * @param n: [int] length of the picture
	 * @param x: [int] reference index x
	 * @param y: [int] reference index y
	 * @param picture: [int[][]] original picture artwork
	 *
	 * @return [int] size of the region
	 */
	private int bfs(int m, int n, int x, int y, int[][] picture)
	{
		int size = 1;
		
		isVisit[x][y] = true;
		
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y });
		
		while (!queue.isEmpty())
		{
			int[] position = queue.poll();
			
			for (int i = 0; i < 4; i++)
			{
				int dx = position[0] + DX[i];
				int dy = position[1] + DY[i];
				
				// If dx and dy are within the overall area and reference index range, share the same color, and haven't been checked yet
				if (dx > -1 && dx < m && dy > -1 && dy < n && picture[dx][dy] == picture[x][y] && !isVisit[dx][dy])
				{
					queue.offer(new int[] { dx, dy });
					
					isVisit[dx][dy] = true;
					
					size++;
				}
			}
		}
		
		return size;
	}
}

DX and DY represent the movement in the x-coordinate and y-coordinate, respectively, for up, down, left, and right.

Even though it represents up/down/left/right, the reason DY is [ -1, 1, 0, 0 ] rather than [ 1, -1, 0, 0 ] is that moving down from picture[0][1] goes to picture[0][2], i.e., the y-value increases by 1.

We declare a method called bfs to perform the BFS algorithm.

Every time an adjacent region with the same color is found, the value is accumulated into size, allowing us to compute the size of the region.