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

알고리즘 스프린트 5일차 - [프로그래머스] Lv 2. 카카오 프렌즈 컬러링북

 

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

프로그래머스

 

소요시간

30분

 

계획

전형적인 라벨링 문제

BFS 활용하여 라벨링하면 되겠다 정도만 생각하고 바로 시작했다

 

풀이

4방향 탐색 하면서 탐색한 지점은 체크해나가는 식으로 접근

탐색 방법 : BFS

 

1. 2차원 배열 돌면서 0이 아닌 지점을 만났을 때, 탐색 했던 지점인지 확인하고

2. 탐색하지 않은 곳일 때 해당 지점의 컬러 값이랑 좌표를 BFS 함수에 전달

3. BFS로 4방향 탐색하면서 같은 컬러 값을 가진 지점들을 체크하고, 체크 될 때마다 카운팅

 

결과

코드

import java.util.*; 

class Solution {
    static boolean[][] check;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static class coord {
		int i, j;
		public coord(int i, int j) {
			this.i = i;
			this.j = j;
		}
	} 
    public int bfs(int i, int j, int m, int n, int color, int[][] picture) {
    	int size = 1;
    	ArrayDeque<coord> q = new ArrayDeque<>();
    	q.add(new coord(i, j));
    	check[i][j] = true;
    	while (!q.isEmpty()) {
			coord temp = q.poll();
			for (int k = 0; k < 4; k++) {
				int nx = dx[k] + temp.i;
				int ny = dy[k] + temp.j;
				if (nx < 0 || nx >= m || ny < 0 || ny >= n || check[nx][ny] || picture[nx][ny] != color) {
					continue;
				}
				check[nx][ny] = true;
				q.add(new coord(nx, ny));
				size++;
			}
		}
    	return size;
    }
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        
        check = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (picture[i][j] != 0 && !check[i][j]) {
					numberOfArea += 1;
					int tempMax = bfs(i, j, m, n, picture[i][j], picture);
					maxSizeOfOneArea = Integer.max(tempMax, maxSizeOfOneArea);
				}
			}
		}
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}

 

마치며

간만에 BFS 4방향 탐색 복습도 하고 좋았는데, Java로 밖에 못푸는 문제라 Java의 기억을 되짚는데 시간이 좀 걸렸다.