프로그래머스_카카오 프렌즈 컬러링북_자바

https://programmers.co.kr/learn/courses/30/lessons/1829

출처

코딩테스트 연습 - 카카오프렌즈 컬러링북

탐색을 통해서 영역의 수를 구하고 각영역의 넓이의 최대값을 구하면되는 문제이다.

재귀로 풀면 스택이 초과하여 통과하지 못한다. 그래서 나는 BFS 로 풀었다.

주의해야하는점

탐색을 진행할때 boolean 형 배열을 두어 이미 방문한곳은 재방문 하지 않게 처리해야한다.

같은 영역을 탐색시 배열값이 같아야한다 (ex picture[1][2] = 5 이고 picture[1][3] = 5 여야지만 같은 영역이다.)

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

public class Solution {
	
	
	 public static int[] solution(int m, int n, int[][] picture) {
	        int numberOfArea = 0;
	        int maxSizeOfOneArea = 0;
	        boolean[][] check = new boolean[m][n];
	        int[] xx = {0, 1, 0, -1};
	        int[] yy = {1, 0, -1, 0};
	        for(int i = 0; i < m; i++) {
	        	for(int j = 0; j < n; j++) {
	        		int max = 0;
	        		if(picture[i][j] != 0 && !check[i][j]) {
	        			numberOfArea++;
	        			max++;
	        			Queue<Kp> q = new LinkedList<Kp>();
	        			q.add(new Kp(i, j));
	        			check[i][j] = true;
	        			int target = picture[i][j];
	        			while(!q.isEmpty()) {
	        				Kp temp = q.poll();
	        				int x = temp.x;
	        				int y = temp.y;
	        			
	        				for(int k = 0; k < 4; k++) {
	        					int new_x = x + xx[k];
	        					int new_y = y + yy[k];
	        					if(new_x >= 0 && new_x < m && new_y >= 0 && new_y < n) {
		        					if(!check[new_x][new_y] && picture[new_x][new_y] == target) {
	        							q.add(new Kp(new_x, new_y));
	        							check[new_x][new_y] = true;
	        							max++;
	        					}
	        					}

	        				}
	        			}
	        			maxSizeOfOneArea = Math.max(maxSizeOfOneArea, max);
	        		}
	        	}
	        }
	        
	        int[] answer = new int[2];
	        answer[0] = numberOfArea;
	        answer[1] = maxSizeOfOneArea;
	        System.out.println(Arrays.toString(answer));
	        return answer;
	    }
}

class Kp{
	int x,y;
	Kp(int x, int y){
		this.x = x;
		this.y = y;
	}
}