[프로그래머스] 카카오프렌즈 컬러링 북 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

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

2. 입력

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

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

3. 예제

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

4. 풀이

문제를 풀려면 영역을 찾아야 합니다.

문제에서 영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다고 하였으므로 현재 위치에서 동서남북으로 연결된 지점의 Color 값이 같으면 같은 영역으로 볼 수 있을 것입니다.

문제에서는 영역의 개수와 영역의 가장 큰 넓이를 구해야 하므로 두 과정을 나누어 설명하겠습니다.

 

• 가장 큰 넓이 구하기
  먼저 가장 큰 넓이를 구하여 메모라이즈 하기 위해 전역 변수로 max를 선언하였습니다.
  

  private int max = 0;​

  
  영역을 구하기 위해서 BFS를 이용하여 시작점에서 연결된 영역의 넓이를 구하였습니다.
  
  먼저 BFS를 이용하기 위해 입력으로 주어진 picture의 2차원 배열 크기와 동일한 Boolean 2차원 배열을 선언하고 초기화하여 줍니다.
  
  

  int[] moveX = {0, 1, 0, -1};
  int[] moveY = {-1, 0, 1, 0};
  Queue<Point> queue = new LinkedList<>();
  
  queue.add(new Point(startX, startY));
  check[startY][startX] = true;

  
  이후 BFS 메서드에서는 상하좌우 이동 계산 좌표를 배열로 선언하고 Queue에 시작 좌표인 x와 y를 Point객체로 만들어 Queue에 추가합니다.
  
  

  int result = 0;
  while(!queue.isEmpty()){
  	Point nowPoint = queue.poll();
  	result++;
  	int color = picture[nowPoint.y][nowPoint.x];
  
  	for(int i=0; i<4; i++){
  		int calcX = nowPoint.x + moveX[i];
  		int calcY = nowPoint.y + moveY[i];
  
  		if(calcX > -1 && calcX < maxX && calcY > -1 && calcY < maxY){
  			if(color == picture[calcY][calcX] && !check[calcY][calcX]) {
  				queue.add(new Point(calcX, calcY));
  				check[calcY][calcX] = true;
  			}
  		}
  	}
  }

  
  Queue에 포함된 좌표는 영역에 포함되는 것이므로 영역의 넓이를 저장하는 변수 result의 값을 1 증가시킵니다.
  
  이후 Queue에서 poll 한 Point객체를 이용하여 해당 좌표의 상하좌우 좌표를 계산합니다.
  
  계산된 좌표가 picture범위에 포함되고 Color값이 시작 좌표의 Color값과 같고 확인하지 않은 좌표인 경우 해당 좌표를 Point 객체로 만들어 Queue에 추가하고 해당 좌표의 check값을 true 변환하여 확인을 완료했다고 표시하여 줍니다.
  
  

  max = Math.max(max, result);​

  
  이후 Queue가 empty가 되면 영역의 가능한 면적을 모두 확인 한 것으로 result의 값을 전역 변수 max와 비교하여 큰 수를 max에 입력합니다.
• 영역의 개수
  

  for(int i=0; i<m; i++){
  	for(int j=0; j<n; j++){
  		if(!check[i][j] && picture[i][j] != 0) {
  			count++;
  			BFS(j, i, check, picture);
  		}
  	}
  }

  
  영역의 개수는 picture의 값이 0이 아닌 곳과 BFS를 통해 영역검사에서 확인을 완료하지 않은 곳의 Count를 확인하면 되므로 picture의 모든 위치를 순회하면서 Color값이 0이 아니면서 영역 확인이 되지 않은 곳의 개수를 Count 합니다.

위에서 구해진 영역의 개수와 영역의 최대 넓이 값을 배열에 담아 return 하면 문제를 풀 수 있습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

private int maxX;
private int maxY;
private int count = 0;
private int max = 0;
public int[] solution(int m, int n, int[][] picture) {
	this.maxX = n;
	this.maxY = m;
	boolean[][] check = new boolean[m][n];

	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			if(!check[i][j] && picture[i][j] != 0) {
				count++;
				BFS(j, i, check, picture);
			}
		}
	}

	return new int[] {this.count, this.max};
}

public void BFS(int startX, int startY, boolean[][] check, int[][] picture){
	int[] moveX = {0, 1, 0, -1};
	int[] moveY = {-1, 0, 1, 0};
	Queue<Point> queue = new LinkedList<>();

	queue.add(new Point(startX, startY));
	check[startY][startX] = true;

	int result = 0;
	while(!queue.isEmpty()){
		Point nowPoint = queue.poll();
		result++;
		int color = picture[nowPoint.y][nowPoint.x];

		for(int i=0; i<4; i++){
			int calcX = nowPoint.x + moveX[i];
			int calcY = nowPoint.y + moveY[i];

			if(calcX > -1 && calcX < maxX && calcY > -1 && calcY < maxY){
				if(color == picture[calcY][calcX] && !check[calcY][calcX]) {
					queue.add(new Point(calcX, calcY));
					check[calcY][calcX] = true;
				}
			}
		}
	}

	max = Math.max(max, result);
}