프로그래머스 - 카카오프렌즈 컬러링 북

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 카카오프렌즈 컬러링 북

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

풀이 : BFS를 이용한 완전 탐색

import java.util.LinkedList;

class Solution {
   static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
  public int[] solution(int m, int n, int[][] picture) {
     int max = 0, num = 0;
		int dx [] = {-1, 1, 0, 0};
		int dy [] = {0, 0, -1, 1};
		boolean [][] chk = new boolean [m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(picture[i][j] == 0 || chk[i][j]) continue; // 방문 여부 판정
				LinkedList <Point> qu = new LinkedList<Point>(); // BFS
				qu.add(new Point(i,j));
				chk[i][j] = true;
				int cnt = 1;
				
				while(!qu.isEmpty()) {
					Point p = qu.poll();
					for (int k = 0; k < 4; k++) { // 상하좌우 탐색
						int x = p.x + dx[k];
						int y = p.y + dy[k];
						if( x < 0 || y < 0 || x >= m || y >= n) continue; // 범위 판정
						if(!chk[x][y] &&  picture[x][y] == picture[p.x][p.y]) {
							chk[x][y] = true;
							cnt++;
							qu.add(new Point(x,y));
						}
					}
				}
				max = Math.max(max, cnt);
				num++;
			}
		}
		int [] ans = new int [2];
		ans[0] = num;
		ans[1] = max;
        return ans;
  }
}