[프로그래머스,Level 2] 카카오프렌즈 컬러링북(JAVA 구현)

- 첫 풀이 및 정답풀이

  우선 주의해야 할 점은 이 문제는 예제 입출력으로 주어진 데이터와 실제 예제 코드를 실행시켰을 때 다른 데이터가 들어온다. 

  보이는 바와 같이 문제에서 설명하고 있는 예제 입출력과 다른 것을 확인할 수 있다. 그렇기 때문에 코드를 짤 때 이를 참고하고 짜는 것이 좋을 것 같다. 본인은 문제에서 제시하는 예제를 바탕으로 짰는데 다른 결과가 나와 놀랐기는 했지만, 어쨌든 제대로 동작하였다. 

---

 

  또한 필자는 문제를 이해하는 데 시간이 좀 걸렸는데, 자세히 설명이 안 나와 있어 그런지 아니면 본인이 이해력이 부족한 건지는 모르겠지만 정리해보면 이 문제에서 말하는 '영역'은 같은 색깔로(여기선 정수로 표현하므로 같은 정수) 상, 하, 좌, 우 연결되어 있다면 하나의 영역으로 간주한다는 것이다. 그렇기 때문에 어피치 그림의 영역의 수는 12개가 된다.(처음에는 이해할 수 없었다. 왜 12개지?)  => 핑크 얼굴색 1개 + 각 눈 3개씩 6개 + 볼터치 2개 + 입꼬리 2개 + 입술1개

 

  여기까지 이해하고 나서 이전에 백준 온라인 저지에서 풀어보았던 '단지 번호 붙이기' 문제와 유사하다는 것을 알 수 있었다. 아래는 이전에 게시한 블로그의 풀이 글.

[백준,BOJ 2667] 단지번호붙이기(JAVA 구현,추가풀이)

  이런 유형의 문제는 DFS, BFS를 통해 연결되어 있는 노드를 방문하며 로직을 처리하는 방식으로 풀이가 가능하다. 필자의 생각으로는 두 개의 방법 중 무엇을 사용하던 상관은 없다고 생각된다. 실제로 DFS, BFS를 활용한 다양한 풀이가 존재한다. 본인은 DFS를 이용해 풀어 보았다. 

---

  마지막으로 주의해야 할 점! 본인과 같이 테스트 케이스는 통과가 되었지만 제출 시 탈락이 나오는 분들은 아마 문제에서 주어지는 변수인 numberOfArea, maxSizeOfOneArea를 전역으로 선언해 사용했을 것이라고 생각된다. 왜인지 모르겠지만 이 변수들을 전역으로 선언하였다면, 꼭! solution 메서드 안에서 초기화를 수행해 주어야 통과가 된다.

 

class Solution {
    // 변수 접근을 위한 전역 변수들.
    static int numberOfArea;
    static int maxSizeOfOneArea;
    // 한 영역의 수를 저장하는 변수.
    static int temp_cnt = 0;
    // 좌표에서의 상,하,좌,우 탐색을 위한 배열.
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    // DFS 메소드
    public static void dfs(int x,int y, int[][] picture, boolean[][] check){
        // 6. 방문한 적 있는 좌표라면 DFS 종료.
        if(check[x][y]) return;
        
        // 7. 처음 방문 시 방문처리.
        check[x][y] = true;
        // 8. 영역의 수 증가.
        temp_cnt++;
        
        // 9. 한 좌표에서 상,하,좌,우 탐색.
        for(int i =0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 10. picture 배열의 범위를 벗어나면 continue.
            if(nx<0 || nx>=picture.length || ny<0 || ny>=picture[0].length) continue;
            
            // 11. 현 좌표의 색 == 상,하,좌,우 좌표의 색 && 방문한적 없는 상,하,좌,우 좌표라면.
            if(picture[x][y] == picture[nx][ny] && !check[nx][ny]){                
                // 12. DFS를 위한 재귀호출.
                dfs(nx,ny,picture,check);
            }            
        }        
    }
    
    public int[] solution(int m, int n, int[][] picture) {
        // 1. 초기화 꼭! 하기.
        numberOfArea =0;
        maxSizeOfOneArea=0;
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        
        // 2. DFS시 방문여부를 체크 할 배열.
        boolean[][] check = new boolean[m][n];
        
        // 3. 주어진 picture 배열을 탐색.
        for(int i =0;i<m;i++){
            for(int j=0;j<n;j++){
                // 4. 원소가 0이 아니고, 방문한 적이 없다면.
                if(picture[i][j] != 0 && !check[i][j]){
                    // 5. 영역의 수가 1개 증가하며 DFS 탐색 수행.
                    numberOfArea++;
                    dfs(i,j,picture,check);
                }
                // 13. 한 영역의 탐색이 모두 끝났다면, 조건에 따라 최대 영역의 수를 변경.
                if(temp_cnt > maxSizeOfOneArea) maxSizeOfOneArea = temp_cnt;
                // 14. 한 영역의 수는 다시 초기화.
                temp_cnt = 0;
            }
        }
        
        // 15. 각 값을 answer 배열에 담아주고 끝.
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        
        return answer;
    }
}