[프로그래머스 Level.2] 카카오프렌즈 컬러링북 (2017 카카오코드 예선) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 2017 카카오코드 예선 > 카카오프렌즈 컬러링북

 

 

 

문제 설명

 

 

카카오 프렌즈 컬러링북

 

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

 

 

위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.

 

 

입력 형식

입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 100
• picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
• picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

 

출력 형식

리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

 

예제 입출력

m	n	picture	answer
6	4	[[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]	[4, 5]

 

예제에 대한 설명

예제로 주어진 그림은 총 4개의 영역으로 구성되어 있으며, 왼쪽 위의 영역과 오른쪽의 영역은 모두 1로 구성되어 있지만 상하좌우로 이어져있지 않으므로 다른 영역이다. 가장 넓은 영역은 왼쪽 위 1이 차지하는 영역으로 총 5칸이다.

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    boolean[][] visited;
    int[] dx = {0, 0, -1, 1}; // 상하좌우
    int[] dy = {1, -1, 0, 0};
    int sizeOfArea = 0;
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0; // 구역의 개수
        int maxSizeOfOneArea = 0; // 제일 큰 구역의 크기

        visited = new boolean[picture.length][picture[0].length];
        
        for(int i=0; i<picture.length; i++) {
            for(int j=0; j<picture[0].length; j++) {
                if(picture[i][j] != 0 && !visited[i][j]) {
                    numberOfArea++;
                    dfs(i, j, picture);
                    // bfs(i, j, picture);
                }
                
                maxSizeOfOneArea = Math.max(maxSizeOfOneArea, sizeOfArea);
                sizeOfArea = 0;
            }
        }
        
        int[] answer = new int[2];
        
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        
        return answer;
    }
    
    public void dfs(int x, int y, int[][] picture) {
        if(visited[x][y]) return;
        
        visited[x][y] = true;
        sizeOfArea++;
        
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < picture.length && ny < picture[0].length) {
                if(picture[x][y] == picture[nx][ny]) {
                    dfs(nx, ny, picture);
                }
            }
        }
    }
    
    public void bfs(int x, int y, int[][] picture) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x, y});
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            sizeOfArea++;
            
            for(int i=0; i<4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < picture.length && ny < picture[0].length) {
                    if(!visited[nx][ny] && picture[nx][ny] == picture[x][y]) {
                        q.add(new int[] {nx, ny});
                        visited[nx][ny] = true;
                    }
                }                                                                                                           
            }
        }
    }
    
}

 

풀이

1. 주어진 picture의 모든 좌표를 확인하면서 좌표의 값이 0이 아니고 visited도 false라면 현재 좌표와 이어진(같은 값인) 좌표들을 전부 visited를 true로 변경하면서 이어진 좌표의 사이즈를 측정하고 마지막 까지 진행하면서 구역의 개수를 카운팅하면 된다.
2.  우선 주어진 picture와 같은 크기로 2차원 boolean형 배열 visited를 생성하고 좌표의 상하좌우로 한 칸씩 이동하기 위해 int형 배열 dx와 dy를 만든다. 그리고 구역의 크기를 측정할 수 있도록 sizeOfArea를 선언한다.
3. 구역의 개수를 나타내는numberOfArea와 제일 큰 구역의 크기를 나타낼 maxSizeOfOneArea를 선언한다.
4. 이제 2차원 배열 picture를 이중 for문을 돌면서 picture의 값이 0이 아니고 visited가 false라면 numberOfArea(구역의 개수)를 1 증가시키고 완전탐색 dfs()를 하여 현재 좌표와 이어진(같은 값인) 좌표들을 카운팅하면서 visited를 true로 변경하고 현재 구역의 개수를 카운팅한 sizeOfArea와 maxSizeOfOneArea와 비교하여 최대값을 업데이트 하고 sizeOfArea를 다시 0으로 초기화하며 모든 좌표를 확인하도록 한다.
5.  dfs()에서는 만약 visited가 true라면 그냥 리턴하고 아니라면 현재 좌표의 visited를 true로 변경하고 sizeOfArea(현재 구역의 개수)를 1 증가시킨다. 그리고 현재 좌표에서 상하좌우로 한칸씩 이동한 좌표를 for문을 돌면서 해당 좌표가 picture의 좌표를 벗어나지 않는다고 좌표의 값이 현재 좌표의 값과 같고 visited가 false라면 해당 좌표로 dfs()를 재귀호출하여 이어진 구역의 개수를 증가시키면서 확인하도록 한다.
6. 이렇게 구역의 개수를 얻고 이어진 구역의 visited를 true로 변경하면서 picture를 돌면서 numberOfArea(총 구역의 개수)와 maxSizeOfOneArea(가장 큰 구역의 크기)를 구해 answer에 저장하고 반환한다.
7. 구역의 크기를 구하는 부분에서 물론 깊이우선탐색 dfs가 아닌 너비우선탐색 bfs를 이용해도 된다. 좌표를 담기 위해 int형 배열을 선언 타입으로 하는 Queue를 생성하고 구역을 탐색하기 위해 해당 좌표를 Queue에 담고 해당 좌표의 visited를 true로 변경한다. 그리고 Queue가 빌 때까지 반복하는 while문을 생성한다. 우선 poll()을 이용하여 Queue의 첫 번째 좌표를 꺼내고 sizeOfArea를 1 증가시킨다. 그리고 꺼낸 좌표의 상하좌우 한 칸씩 이동한 좌표를 탐색하기 위한 for문을 만든다. 해당 좌표의 상하좌우로 한 칸씩 이동한 좌표를 만들고 이 좌표가 picture의 좌표 범위를 벗어나지 않고 좌표의 값이 현재 좌표의 값과 같고 visited가 false라면 해당 좌표를 Queue에 담고 담은 좌표의 visited를 true로 변경하며 상하좌우 좌표를 탐색하면서 while문을 진행하면 해당 좌표에서 이어진 구역을 탐색 할 수 있다.