Level2_카카오프렌즈 컬러링북 (JAVA)

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

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

class Solution {
    static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static boolean[][] visited;
	static int numberOfArea = 0; //영역 수
	static int maxSizeOfOneArea = 0; //가장 큰 영역의 넓이
	static int cnt = 0;
    
    static class XY {
		int x;
		int y;
		public XY(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
    
    public static int[] solution(int m, int n, int[][] picture) {
        numberOfArea = 0;
	    maxSizeOfOneArea = 0;
		visited = new boolean[m][n];

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j] && picture[i][j] != 0) {
					cnt = 1;
					numberOfArea++;

					maxSizeOfOneArea = Math.max(maxSizeOfOneArea, bfs(i, j, picture));
				}
			}
		}

		int[] answer = new int[2];
		answer[0] = numberOfArea;
		answer[1] = maxSizeOfOneArea;
		return answer;
	}
    
    private static int bfs(int a, int b, int[][] picture) {
		Queue<XY> q = new LinkedList<>();
		q.offer(new XY(a, b));
		visited[a][b] = true;
		cnt = 1;

		while (!q.isEmpty()) {
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();

			for (int i = 0; i < 4; i++) {
				int xx = x + dx[i];
				int yy = y + dy[i];

				if (xx >= 0 && xx < picture.length && yy >= 0 && yy < picture[0].length) {
					if(picture[xx][yy] == picture[x][y] && !visited[xx][yy]) {
						visited[xx][yy] = true;

						cnt++;
						q.offer(new XY(xx, yy));
					}
					if(picture[xx][yy] != picture[x][y])
						continue;
				}
			}
		}
		return cnt;
	}
}

 

 

1. picture[][] 배열의 0이 아닌 수를 만나면 - 영역개수++, BFS를 돌린다.

 

2. picture[i][j]값과 같은 값들을 탐색하고 더이상 없을 경우에 BFS에서 빠져나오기 때문에, 영역의개수를 증가시킨것!

 

3. BFS의 리턴값으로 해당 영역의 넓이를 리턴하여 - max값을 찾는다.