Java로 알고리즘 - [프로그래머스] 컬러링북

원태연·2022년 6월 30일

Java algorithm

Algorithm문제

목록 보기

2/10

카카오 프렌즈 컬러링북

원본 : https://programmers.co.kr/learn/courses/30/lessons/1829?language=java

문제

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.

입력 형식

입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.

( $1 <= m$ , $n <= 100$ )
picture의 원소는 0 이상 ( $2^{31} - 1$ ) 이하의 임의의 값이다.
picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

출력 형식

리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

Test Case

input

m - 6
n - 4
picture - [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]

output

answer - [4, 5]

풀이

흔히 접할 수 있는 BFS로 접근하였다.
주어진 2차원 배열 pictures를 모두 방문하면서 BFS Search를 통해 연속된 영역과 그 크기를 구하였다.

pictures[0][0]을 기준으로 pictures[m][n]까지 모두 방문하며 BFS Search를 시작했다.

과정은 다음과 같다.

아래와 같은 예시의 컬러링북이 있고, 최초 실행시 $(0,0)$ 부터 BFS탐색을 시작할 것이다.

탐색 순서 Queue
Queue : ${(0,0)}$

(0,0) 기준으로 상하좌우를 탐색한다.
순서는 편의상 (오른쪽, 아래, 왼쪽, 위)

상하좌우를 방문 하면서, 숫자가 같다면(동일한 영역)이라면 탐색해야할 큐에 추가한다.
이때, 방문을 완료했음을 표기하기 위해 탐색했던 위치는 0으로 변경한다.

탐색 순서 Queue
Queue : $\{(0, 0), (1, 0), (0, 1)\}$
(0,0)에서 상하좌우를 모두 방문했으면, Queue에서 poll() 한다.

탐색 순서 Queue
Queue : $\{(1, 0), (0, 1)\}$
Queue가 비어있을 때 까지 반복한다.
다음 과정을 진행하면, (1, 0)을 기준으로 상하좌우를 방문하여 탐색한다. 모든 영역을 방문하여 더이상 탐색 대상이 없는 경우, Queue가 비어지게 된다.

위 과정이 (0,0)을 기준으로 BFS Search한 결과이다.

이 과정이 끝난 뒤, (1, 0)을 기준으로 BFS Search를 수행하면 바로 종료된다. 이미 방문했기 때문에 0으로 되어있기 때문이다.

그러다가, 2가 나오는 지점인 (3,3)에서 탐색을 시작할 것이다.

이러한 방식으로 영역을 찾고, 코드로 구현해보자.

구현 코드

우선, BFS Search의 시점이 될 picture[i][j]를 방문하자

	public int[] solution(int m, int n, int[][] picture) {
		int numberOfArea = 0; //영역의 개수
		int maxSizeOfOneArea = 0; //최대 영역의 크기

		//picture의 모든 위치 방문
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
            	//(i, j)
				int colorNum = picture[i][j]; 

				if (colorNum == 0) { //0이면 탐색 없이 넘어가기
					continue;
				}
				int areaSize = searchArea(i, j, picture, colorNum); //(i,j)에서 탐색
				if (maxSizeOfOneArea < areaSize) { //최댓값 반영
					maxSizeOfOneArea = areaSize;
				}

				numberOfArea++; //탐색이 이루어 지면 영역의 갯수 +1 하기
			}
		}

		int[] answer = new int[2];
		answer[0] = numberOfArea;
		answer[1] = maxSizeOfOneArea;
		return answer;
	}

시작 좌표로 부터 영역을 찾는 부분(BFS Search)


//				   | 좌 | 하 | 우 | 상 |
private int[] dx = {-1,  0,   1,   0}; 
private int[] dy = {0 ,  1,   0,  -1};


private int searchArea(int startY, int startX, int[][] picture, int colorNum) {
		Queue<Direction> queue = new LinkedList<>(); //탐색해야 하는 위치를 저장하는 큐
		int xLimit = picture[0].length; //picture의 마지막 x좌표
		int yLimit = picture.length;  //picture의 마지막 y좌표

		//시작 지점부터 탐색 시작
		queue.add(new Direction(startX, startY));
		
        //제자리 방문 반영
		int areaSize = 1;
		picture[startY][startX] = 0;

		while (!queue.isEmpty()) {
			Direction d = queue.poll(); //상하좌우 탐색할 위치 poll하기

			for (int i = 0; i < 4; i++) {
				int dx = d.getX() + this.dx[i]; //현재 위치에서 i에 따라 상하좌우 탐색
				int dy = d.getY() + this.dy[i]; 

				//picture의 범위를 벗어난 경우
				if (dx < 0 || dy < 0 || dx >= xLimit || dy >= yLimit) {
					continue;
				}
				
                //탐색하는 영역이 같은 색인 경우
				if (picture[dy][dx] == colorNum) {
					areaSize++; //크기 +1
					picture[dy][dx] = 0; //방문 유무 표기
					queue.add(new Direction(dx, dy)); //탐색해야할 위치로 추가
				}
			}
		}

		return areaSize;
	}
    
class Direction {
	private int x;
	private int y;

	public Direction(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}
}

전체 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Programmers_FriendsColoringBook {
	public static void main(String[] args) {
    //임의의 입력 케이스
		Solution sol = new Solution();
		int m = 6;
		int n = 6;
		int[][] picture = {
			{1, 1, 1, 0, 0, 0},
			{1, 2, 2, 0, 0, 0},
			{1, 0, 0, 1, 1, 1},
			{0, 0, 0, 1, 1, 1},
			{0, 0, 0, 3, 3, 1},
			{0, 0, 0, 3, 1, 1}
		};
		int[] answer = sol.solution(m, n, picture);

		System.out.println(Arrays.toString(answer));
	}
}

class Solution {

	private int[] dx = {-1, 0, 1, 0}; // 위, 오른, 아래, 위 방향
	private int[] dy = {0, 1, 0, -1}; // 위, 오른, 아래, 위 방향
	public int[] solution(int m, int n, int[][] picture) {
		int numberOfArea = 0;
		int maxSizeOfOneArea = 0;

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int colorNum = picture[i][j];
				if (colorNum == 0) {
					continue;
				}
				int areaSize = searchArea(i, j, picture, colorNum);
				if (maxSizeOfOneArea < areaSize) {
					maxSizeOfOneArea = areaSize;
				}

				numberOfArea++;
			}
		}

		int[] answer = new int[2];
		answer[0] = numberOfArea;
		answer[1] = maxSizeOfOneArea;
		return answer;
	}

	private int searchArea(int startY, int startX, int[][] picture, int colorNum) {
		Queue<Direction> queue = new LinkedList<>();
		int xLimit = picture[0].length;
		int yLimit = picture.length;

		queue.add(new Direction(startX, startY));

		int areaSize = 1;
		picture[startY][startX] = 0;

		while (!queue.isEmpty()) {
			Direction d = queue.poll();

			for (int i = 0; i < 4; i++) {
				int dx = d.getX() + this.dx[i];
				int dy = d.getY() + this.dy[i];

				if (dx < 0 || dy < 0 || dx >= xLimit || dy >= yLimit) {
					continue;
				}

				if (picture[dy][dx] == colorNum) {
					areaSize++;
					picture[dy][dx] = 0;
					queue.add(new Direction(dx, dy));
				}
			}
		}

		return areaSize;
	}

	class Direction {
		private int x;
		private int y;

		public Direction(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int getX() {
			return x;
		}

		public int getY() {
			return y;
		}
	}
}