[프로그래머스/자바] 카카오프렌즈 컬러링북 풀이 - 2017 카카오코드 예선

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

프로그래머스

2017 카카오코드 예선 Level 2 문제다.

 

DFS나 BFS로 쉽게 풀 수 있는 문제다.

문제에 오류가 있는지 static 변수인 cnt와 max를 solution안에 초기화를 했을 때 정답처리 되었다.

 

solution 함수 밖에서도 m, n, picture를 사용하기 위해

static으로 int M, N, int[][] pictures를 선언하고 대입해주었다.

 

그리고 picture의 원소 하나하나 탐색한다.

색칠되어 있고 아직 방문하지 않았다면, 새로운 영역인 것이므로 

영역의 갯수 cnt를 1 증가한다.

해당 영역의 넓이를 구하기 위해 static 변수 width를 0으로 선언하고 DFS를 진행한다.

 

 

DFS로 상하좌우 이동해가며 현재 색칠되어 있는 영역과 동일한 숫자라면 계속 진행해가며

넓이를 1씩 증가시킨다.

이때 넓이를 DFS의 매개변수로 전달하면 한번의 DFS에서 여러 방향으로 갈때 넓이가 제대로 반영되지 않기 때문에

꼭 static으로 넓이를 선언해주어야 한다.

또한 다른 영역의 넓이를 다시 계산해야 할때 넓이를 다시 0으로 변경해주는 것이 중요하다.

 

한 영역의 DFS가 끝났다면 그 영역의 넓이를 모두 구한 것이므로

max와 넓이 width를 비교해서 더 큰 값을 max에 대입한다.

 

 

 

class Solution {
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int cnt;
    static int max;
    static int width;
    static boolean[][] visit;
    static int[][] pictures;
    static int M, N;
    
    public int[] solution(int m, int n, int[][] picture) {
        cnt = 0; max = 0;
        M = m; N = n; pictures = picture;
        visit = new boolean[m][n];

        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(picture[i][j] != 0 && !visit[i][j]) { // 색칠되어 있고 아직 방문하지 않은 곳이면 새로운 영역을 의미
                    width = 0;
                    visit[i][j] = true; 
                    DFS(i, j, picture[i][j]); // 색칠된 위치와 값으로 DFS
                    max = Math.max(width, max); // DFS로 탐색한 영역의 넓이를 max와 비교해 대입
                    cnt++; // 영역의 갯수 더하기
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = cnt;
        answer[1] = max;
        return answer;
    }
    
    static void DFS(int x, int y, int value) {
        width++; // DFS를 진행할 때마다 넓이 1씩 증가
        
        for(int i=0;i<4;i++) {
            // 상하좌우로 탐색
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            
            // 탐색하려는 위치가 범위 내에 존재하고 방문하지 않았으며, 현재 영역의 값과 같은 값으로 색칠되어 있다면
            if(isNext(nextX, nextY) && !visit[nextX][nextY] && pictures[nextX][nextY] == value) {
                visit[nextX][nextY] = true;
                DFS(nextX, nextY, value); 
            }
        }
    }
    
    // 탐색하려는 곳이 picture 배열 내에 있는지 확인
    static boolean isNext(int x, int y) {
        if(x < M && x >= 0 && y < N && y >= 0)
            return true;
        return false;
    }
}