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

문제

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

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

 

풀이

백준으로 많이 풀어본 유형이긴 한데 별 생각없이 귀찮은 변수나 배열 등을 걍 다 static으로 때려박아서 결코 좋은 풀이는 아닌 것 같다 ,,, ㅎㅎㅎ

 

그리고 다 풀고 테케까지 다 맞았는데 틀리다고 나와서 질문하기 게시판 보니까 static 애들은 solution() 함수 안에서 초기화 해줘야 한다고 하더라??? 왜 그런지는 모름 암튼 그렇다고 함 ㅋㅋㅋㅋㅋ

이걸 보시는 분들은 알아두면 좋을 듯 하다 !

 

visited[][]로 방문 체크 안해줄거면 방문하면서 숫자들을 0이나 -1 등으로 바꿔주면서 하면 visited[][]는 만들 필요는 없을 것이다 !

나머지는 그냥 2차원 배열 탐색 문제!

물론 bfs로도 풀 수 있음 !

 

자세한건 주석으로!

 

 

코드

// 코딩테스트 연습 - 2017 카카오코드 예선 - 카카오프렌즈 컬러링북
// https://programmers.co.kr/learn/courses/30/lessons/1829

package PROGRAMMERS.level2;

public class Num1829_카카오프렌즈컬러링북2 {
    private static class Solution {
        static int count; // 각 영역에 몇칸인지 count
        static int max; // 각 영역 중 가장 크기가 큰애는 몇칸인지
        static int areaCount; // 영역의 개수가 몇개인지
        static int[][] pictureCopied;
        static boolean[][] visited; // 방문 체크
        static int[] dr;
        static int[] dc;
        static int N, M; // 가로, 세로

        private int[] solution(int m, int n, int[][] picture) {
            count = 0;
            max = Integer.MIN_VALUE;
            areaCount = 0;
            pictureCopied = picture;
            N = n;
            M = m;
            visited = new boolean[M][N];
            dr = new int[]{0, 1, 0, -1};
            dc = new int[]{1, 0, -1, 0};

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 0이 아니고, 방문 전이면
                    if (picture[i][j] != 0 && !visited[i][j]) {
                        dfs(i, j, picture[i][j]);
                        max = Math.max(max, count); // 가장 큰 영역의 크기 최신화
                        count = 0; // 영역의 크기 초기화
                        areaCount++; // 영역의 개수 ++
                    }
                }
            }

            int[] answer = new int[2];

            answer[0] = areaCount;
            answer[1] = max;

            return answer;
        }

        private void dfs(int r, int c, int temp) {
            if (visited[r][c]) { // 이미 방문했으면 return
                return;
            }
            count++; // 같은 영역이면 칸 수 ++
            visited[r][c] = true; // 방문했다고 체크
            
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                // 범위 밖이면 continue
                if (nr < 0 || nr >= M || nc < 0 || nc >= N) {
                    continue;
                }

                // 다음 칸이 같은 색의 영역이면 dfs
                if (pictureCopied[nr][nc] == temp) {
                    dfs(nr, nc, pictureCopied[nr][nc]);
                }
            }
        }
    }



    public static void main(String[] args) {
        Solution s = new Solution();
        int m = 6, n = 4;
        int[][] picture = {{1,1,1,0}, {1,2,2,0}, {1,0,0,1}, {0,0,0,1}, {0,0,0,3}, {0,0,0,3}};

        System.out.println(s.solution(m,n,picture)[0] + " " + s.solution(m,n,picture)[1]);
    }
}