[프로그래머스] 카카오프렌즈 컬리링북

문제

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

 

풀이

색깔 영역 갯수와 가장 큰 영역의 넓이를 계산해야한다.

DFS 방식으로 해결했다.

같은 색깔 영역을 깊이 탐색으로 조사하여, 영역의 넓이까지 계산한다.

 

한 영역을 탐색하는 과정은 아래와 같다.

- 한 블럭에 들어간다 -> 탐색 색깔로 지정한다 -> (위 or 아래 or 왼 or 오른쪽 블럭에 들어간다. -> 탐색 색깔과 같은 색깔인지 확인한다) 여길 반복

 

picture가 가질 수 있는 값에 -1을 추가해서 탐색완료된 영역에 대한 정보를 갖도록 했다.

picture의 값은 아래와 같이 값을 가질 수 있다.

• 0 : 색칠하지 않는 영역(문제 정의)
• 1 이상 : 숫자별로 하나의 색깔을 의미(문제 정의)
• -1 : 탐색완료(유저 정의)

연결된 영역을 탐색하는 반복함수

• 재귀 함수로 작성했다.(메소드 dfs)
• 파라미터로 다음 정보를 가진다.
  • color : 탐색하고 있는 색깔
  • i : 현재 탐색하는 위치의 행 인덱스
  • j : 현재 탐색하는 위치의 열 인덱스
  • m : 총 행 개수
  • n : 총 열 개수
  • picture : 전체 매트릭스(컬러링 그림)
  • cnt : 탐색한 영역의 크기
• 탐색할 인덱스가 매트릭스의 영역을 초과하는지 확인
• 탐색하는 영역이 탐색 색상인지 확인
• 탐색한 영역을 탐색완료로 변경하고 탐색 영역 크기 증가
• 이때까지의 context 정보를 가지고 위, 아래, 왼, 오른쪽 탐색하도록 재귀 호출한다.
• 영역 크기를 반환한다.

제출 결과 정확성 테스트에서 오류가 발생했다.

solution 메소드의 picture 인자의 값을 변경하면 테스트 통과가 불가능하다고한다.

새로운 2d array를 생성해서 값을 복사하니까 정상적으로 동작했다.

 

다른 풀이에도 구현의 차이만 있을 뿐 dfs or bfs 탐색방법을 이용했다.

 

 

소스코드

github

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        // 인자로 전달된 picture를 변경하면 오류발생, 배열 복사
        int[][] newPicture = new int[picture.length][picture[0].length];
        for(int i=0; i<picture.length; i++) {
            for(int j=0; j<picture[i].length; j++) {
                newPicture[i][j] = picture[i][j];  
            }
        }
        
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        for(int i=0; i < m; i++) {
            for(int j=0; j<n; j++) {
                if(newPicture[i][j] > 0) {
                    numberOfArea++;
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, dfs(newPicture[i][j],i,j,m,n,newPicture,0));
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    /**
     * 
     * @param color 탐색 색깔
     * @param i 현재 행 위치
     * @param j 현재 열 위치
     * @param m 총 행 개수
     * @param n 총 열 개수
     * @param picture 컬러링 현황이 있는 2차원 배열
     * @param cnt 탐색한 영역 크기
     * @return 탐색한 영역 크기
     */
    public int dfs(int color, int i, int j, int m, int n, int[][] picture, int cnt) {
        if(i < 0 || i >= m || j < 0 || j >= n) {    // boundary check
            return cnt;
        }
        if(picture[i][j] <= 0 || picture[i][j] != color) {  // 컬러링 영역 여부 확인, 탐색중인 컬러 여부 확인
            return cnt;
        }
        picture[i][j] = -1; // -1는 visited를 의미한다
        cnt++;
        cnt = dfs(color, i+1, j,m,n, picture, cnt);
        cnt = dfs(color, i-1, j,m,n, picture, cnt);
        cnt = dfs(color, i, j+1,m,n, picture, cnt);
        cnt = dfs(color, i, j-1,m,n, picture, cnt);
        return cnt;
    }
}