카카오프렌즈 컬러링북

Posted on Edited on In , ,

문제정의

상하좌우 중 한 방향으로라도 같은 색깔이 칠해진 곳을 같은 영역이라 정의할 때, 영역의 개수와 최대 영역 넓이를 반환하는 함수를 만드는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class KaKaoFriendColoringBook {
    
    //프로그래머스 문제풀이 level2 카카오프렌즈 컬러링북

    public static void main(String[] args)
    {
        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}
        };
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[] answer = new int[2];
        boolean[][] visited = new boolean[m][n];
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j<n; j++)
            {
                if(visited[i][j] == false && picture[i][j] != 0)
                {
                    numberOfArea++;
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, getRegion(visited, i, j, picture, 0, picture[i][j], m, n));
                }
            }
        }        
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

    }
    public static int getRegion(boolean[][] visited, int r, int c, int[][] picture, int area, int c_id, int m, int n)
    {
        if(r == m || c == n || r < 0 || c < 0)
            return area;
        if(picture[r][c] != c_id)
            return area;
        else if(visited[r][c] == true)
            return area;
        else
        {
            visited[r][c] = true;
            area++;
            int left = getRegion(visited, r, c-1, picture, 0, c_id, m, n);
            int right = getRegion(visited, r, c+1, picture, 0, c_id, m, n);
            int up = getRegion(visited, r-1, c, picture, 0, c_id, m, n);
            int down = getRegion(visited, r+1, c, picture, 0, c_id, m, n);
            
            return area+left+right+up+down;
        }
    }
}
단순 탐색이기 때문에 리컬시브 함수만 이용한다면 빠르게 풀 수 있다. 필자는 getRegion을 통해 한 영역의 넓이를 계산할 생각이다. 리컬시브 코드를 볼 때는 항상 종료 조건을 잘 봐야한다. 어떠한 로봇이 있다고 상상하고 그 로봇이 동시에 한 블럭에서 동시에 상하좌우로 뻗어나가며 같은 영역인지 판단한다고 해보자. 그렇다면 3가지의 종료 조건을 생각할 수 있다. 1. 로봇이 그림 밖으로 나갔을 경우 2. 다른 색깔이 칠해져있는 경우 3. 이미 다른 로봇이 지나갔던 곳일 경우 이를 세가지의 if문으로 표시하였다. c_id는 현재 영역의 색깔을 나타내고 visited는 그 영역이 첫방문인지 알려주는 변수이다. 이 종료조건을 모두 통과했을 경우 현재 로봇이 서 있는 곳은 같은 영역으로 표시해야하는 것이다. 이럴 경우 방문했다는 것을 알려주기 위해 해당 visited를 true로 바꿔주고, area를 늘린다. 그리고 그 위치에서 상하좌우로 로봇을 보내기 위해 함수를 호출한다. 전체 영역은 현재 영역에서 상하좌우로 이어진 영역의 합을 구하는 것이므로 left,up,down,right에 각각의 영역을 담아 더하면 된다.

시간복잡도는 모든 영역이 칠해져 있을 때가 최악의 경우이다. 왜냐하면 mxn영역을 다보는데 mxn번 만큼 함수가 계속 호출되기 때문이다. 따라서 최종 시간복잡도는 \(O((m*n)^2)\)이다.

테스트