[프로그래머스, Level2] 카카오프렌즈 컬러링(JAVA)

 

 

필자는 이 문제를 이해하는데 시간이 꽤나 오래 걸렸다..

문제에서 말하는 영역이 이해가 잘 되지 않았는데 문제의 영역은 아래의 설명과 같다.

 

해당 문제에서 말하는 '영역'은 같은 색상(0이 아닌 같은 정수)으로 상, 하, 좌, 우 인접한 칸이 있는 경우 한 영역으로 간주한다.

즉 예제에서의 영역 12개는 핑크 얼굴색 1개 + 검은색 눈 3개 x 2(6개) + 양쪽 볼 진한 핑크 2개 x 검은색 입꼬리 2개 x 검은색 입술 1개로 12개의 영역이 된다.

 

그러므로 위 문제는 해당 사진의 영역과 각 영역 중 가장 큰 영역을 answer 배열에 담아서 리턴하면 되는 문제이다.

 

프로그래머스

 

코드 풀이

class Solution {
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우
    static int[] dy = {0, 0, -1, 1}; // 상하좌우
    static boolean[][] visited;
    static int sizeOfOneArea; // 한 영역의 사이즈

    // 한 영역의 사이즈 구하고, 방문한 노드는 체크하는 역할
    static void dfs(int x, int y, int[][] picture) {

        // 방문 체크
        visited[x][y] = true;
        // 해당 영역의 사이즈 증가
        sizeOfOneArea++;

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

            // 이동할 칸이 배열의 범위 벗어 나거나 방문한 적이 있으면 continue
            if (nx < 0 || picture.length <= nx || ny < 0 ||
            	picture[0].length <= ny ||
                visited[nx][ny]) {
                
                continue;
            }

            // 다음 칸이 해당 영역에 포함이 되면(같은 수)
            if (picture[x][y] == picture[nx][ny]) {
                // 다음칸 이동 가능
                dfs(nx, ny, picture);
            }
        }

    }

    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

        // 방문 체크 배열 생성
        visited = new boolean[m][n];

        // picture 탐색
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 해당 칸이 0 아니고, 방문한 적 없음
                if (picture[i][j] != 0 && !visited[i][j]) {
                    numberOfArea++; // 영역 증가
                    dfs(i, j, picture);
                }
                // 한영역 탐색 끝난 후 최대값 비교
                maxSizeOfOneArea = Math.max(maxSizeOfOneArea, sizeOfOneArea);

                // 한 영역 탐색 끝났으므로 영역의 수 초기화
                sizeOfOneArea = 0;
            }
        }

        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

        return answer;
    }
}