[프로그래머스 알고리즘] 3단계 - 카카오 프렌즈 컬러링북 (런타임 오류가 발생하면, StackOverFlow를 의심해라!)

프로그래머스 3단계 카카오 프렌즈 컬러링북 문제

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

문제설명

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. 

영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

제한사항

1 <= m, n <= 100

picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다. picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

입출력 예

m	n	picture	answer
6	4	[[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]	[4, 5]

입출력 예 설명

예제로 주어진 그림은 총 4개의 영역으로 구성되어 있으며, 왼쪽 위의 영역과 오른쪽의 영역은 모두 1로 구성되어 있지만 상하좌우로 이어져있지 않으므로 다른 영역이다. 가장 넓은 영역은 왼쪽 위 1이 차지하는 영역으로 총 5칸이다

자바코드

 (1) Recursive 사용 - StackOverflow 발생

       
    public static int[] solution(int m, int n, int[][] picture) {
        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(picture[i][j] > 0) {
                    int count = getEqualSpaceCount(visited, picture, picture[i][j] , i, j);
                    answer[0] = count > 0 ? answer[0] + 1 : answer[0];
                    answer[1] = Math.max(count, answer[1]);
                }
            }
        }

        return answer;
    }

    public static int getEqualSpaceCount(boolean[][] visited, int[][] picture, int value, int i, int j) {
        if(i < 0 || i >= picture.length || j < 0 || j >= picture[0].length 
               ||  visited[i][j] == true || value != picture[i][j]) {
            return 0;
        } else {
            visited[i][j] = true;
            return 1 + getEqualSpaceCount(visited, picture, value, i - 1, j)
                     + getEqualSpaceCount(visited, picture, value, i + 1, j)
                     + getEqualSpaceCount(visited, picture, value, i, j - 1)
                     + getEqualSpaceCount(visited, picture, value, i, j + 1);
        }
    }

 (2) Stack 사용 - 문제 해결

 
    public static int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        boolean[][] visited = new boolean[m][n];
        Stack stackX = new Stack<>();
        Stack stackY = new Stack<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = 0;
                if(picture[i][j] > 0 && visited[i][j] == false) {
                    plus(stackX, stackY, visited, j, i);
                    count++;
                    answer[0]++;
                }
                while(!stackX.isEmpty()) {
                    int x = stackX.pop();
                    int y = stackY.pop();
                    // 위 이동
                    if(y > 0 && picture[y - 1][x] == picture[i][j] && visited[y - 1][x] == false) {
                        plus(stackX, stackY, visited, x, y - 1);
                        count++;
                    }
                    // 좌측 이동
                    if(x > 0 && picture[y][x - 1] == picture[i][j] && visited[y][x - 1] == false) {
                        plus(stackX, stackY, visited, x - 1, y);
                        count++;
                    }
                    // 아래 이동
                    if(y < m - 1 && picture[y + 1][x] == picture[i][j] && visited[y + 1][x] == false) {
                        plus(stackX, stackY, visited, x, y + 1);
                        count++;
                    }
                    // 우측 이동
                    if(x < n - 1 && picture[y][x + 1] == picture[i][j] && visited[y][x + 1] == false) {
                        plus(stackX, stackY, visited, x + 1, y);
                        count++;
                    }
                }
                answer[1] = Math.max(answer[1], count);
            }
        }

        return answer;
    }

    public static void plus(Stack stackX, Stack stackY, boolean[][] visited, int j, int i) {
        stackX.add(j);
        stackY.add(i);
        visited[i][j] = true;
    }

코드설명

이 문제는 깊이 탐색 알고리즘을 활용해야만 해결이 가능한 문제이다. 깊이탐색 알고리즘의 풀이방법은 두 가지가 있다. 

첫번째가 재귀함수를 활용, 두번째는 스택 활용이다. 우선, 코드가 간결한 재귀함수를 이용해서 구현을 했다.

그리고 두가지 방식 모두 이전에 방문했던 위치를 기억하는 배열이 공통적으로 필요하다. 나는 visited라는 boolean 타입에 2차원 배열로 생성했다. 

하지만, 재귀함수를 사용했을 경우, 테스트 코드는 통과하지만 채점을 했을 때 시작도 하기전에 런타임 오류가 계속해서 발생했다. 

계속되는 런타임 오류로 문제에서 주어진 최대값으로 테스트 할 때, StackOverflow가 발생한 것을 확인했다.  

원인은 재귀함수가 호출될 때, 호출되는 함수는 Stack 영역에 계속 쌓이는데, Stack 에 너무 많은 메소드가 쌓여서 오류가 발생했다.

문제에서 주어진 최대값으로 테스트 할 때, StackOverflow가 발생했다. 

그래서, 두번째 방식인 스택을 활용했다. 스택을 이용하면, StackOverflow는 발생하지 않지만, 재귀함수에 비해 코드가 간결하지 못하다.

스택을 활용할 때, X, Y좌표를 가지고 있는 각각의 스택을 생성했다. x, y좌표를 변수로 가지는 클래스를 생성할까도 생각했지만, 스택을 두개 사용했다.

그리고 공통적인 부분은 plus 메소드를 구현해서 중복성을 제거했다!

Pain Point

재귀함수로 분명 해결할 수 있을거라고 생각한다. 재귀함수를 통해서 해결하기 위해서는 특정 조건을 더 부여해서, 재귀함수가 호출되는 부분을 제어해서

이전보다 적게 호출되게 구현해야 할거 같다. 이 문제를 풀면서 나뿐만 아니라 많은 사람들이 런타임 오류로 많이 고생한 것을 확인했다. 

만약 재귀로 런타임 오류가 발생한 사람이 있다면, StackOverflow를 의심해봐라!