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

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

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

문제접근

BFS를 이용해서 같은 색상을 가진 인접한 노드들을 탐색하고 영역과 영역의 크기를 구하였다.
그리고 좌표값과 해당 좌표의 색상 정보를 가진 XY클래스를 만들어서 Queue를 이용할 때 편하도록 하였다.

Code

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

class Solution {
    class XY {
        int x;
        int y;
        int value; // 해당 좌표의 그림
        XY(){};
        XY(int x, int y, int value){
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }
    boolean isIn(int x, int y, int m, int n){
        // 영역을 벗어나는지 검사하는 함수
        return (x <0 || x>=m || y < 0 || y >=n);
    }
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[][] visited = new int[m][n]; //방문한 위치인지 기록(1이면 이미 방문한 위치)
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};
        Queue<XY> q = new LinkedList<>();
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                int size=0;
                if(picture[i][j] != 0 && visited[i][j]==0){
                    q.add(new XY(i,j,picture[i][j]));
                    visited[i][j] = 1;
                    numberOfArea++;
                }
                while(!q.isEmpty()){
                    // BFS를 사용하여 영역 찾기
                    XY cur = q.poll();
                    size++;
                    for(int k =0; k<4; k++){
                        // dx, dy를 이용하여 현재 위치의 상하좌우를 탐색
                        int next_x = cur.x + dx[k];
                        int next_y = cur.y + dy[k];
                        if(isIn(next_x, next_y, m, n)){
                            continue;
                        }
                        int next_v = picture[next_x][next_y];
                        if(next_v == cur.value 
                           && visited[next_x][next_y]==0){
                            q.add(new XY(next_x,next_y, next_v));
                            visited[next_x][next_y] = 1;
                        }
                    }
                }
                if(size > maxSizeOfOneArea) maxSizeOfOneArea = size;
            }
        }
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

문제를 보고 BFS를 떠올리긴 했지만, 어디서 큐에 데이터를 추가할 지 어떻게 탐색할 지는 조금 고민을 했던 것 같다.
그리고 인덱스를 벗어난 에러가 떠서 isIn 메소드를 추가하였고, 다른 부분들도 메소드로 빼려고 했으나, BFS 부분을 메소드로 만들려면 너무 많은 변수들을 매개변수로 해줘야해서 안하는게 더 깔끔한 것 같다.(필요성을 못 느끼겠다.)