2017 카카오페스티벌 예선 문제 1 - 카카오프렌즈 컬러링북 풀이

출처: http://t1.kakaocdn.net/codefestival/preliminary.pdf

이번에 풀어볼 문제는 다음과 같습니다.

이번 문제를 풀 때 DFS search를 써서 인접한 영역들을 찾아내고 그 크기를 계산하는 것을 시도했습니다.

class Solution {

    public static int m,n;

    public static int[][] picture;

    public static boolean visited[][];

    public static int size=0;

    public int[] solution(int m, int n, int[][] picture) {

        int numberOfArea = 0;

        int maxSizeOfOneArea = 0;

        //TODO 1: 다른 함수에서 데이터에 접근하기 위해 전역변수취급을 해줍니다. 

        this.m=m;

        this.n=n;

        this.picture=picture;

        this.visited=new boolean[m][n];



        /*

        TODO 2

        반복문을 통해서 새로 탐색할 부분을 찾고, 

        serch함수(영역의 크기계산 & 탐색한 부분은 visited배열에서 true로 처리합니다.

        그리고 최대 영역크기를 갱신합니다.

        */

        for(int r=0;r<m;r++){

            for(int l=0;l<n;l++){

                if(visited[r][l]==false && picture[r][l]!=0 ){

                    searchSize(r,l);

                    numberOfArea++;

                    if(size>maxSizeOfOneArea)   maxSizeOfOneArea=size;

                    size=0;

                }

            }

        }

        int[] answer = new int[2];

        answer[0] = numberOfArea;

        answer[1] = maxSizeOfOneArea;

        return answer;

    }

    public static int searchSize(int r,int l){

        // TODO 3: searchSize함수는 DFS search로 상하좌우 영역을 탐색합니다.

        size++;

        visited[r][l]=true;

        if(r>0 && visited[r-1][l]==false &&picture[r-1][l]==picture[r][l]){

            searchSize(r-1,l);

        }

        if(r<m-1 && visited[r+1][l]==false &&picture[r+1][l]==picture[r][l]){

            searchSize(r+1,l);

        }

        if(l>0 && visited[r][l-1]==false && picture[r][l-1]==picture[r][l]){

            searchSize(r,l-1);

        }

        if(l<n-1 && visited[r][l+1]==false &&picture[r][l+1]==picture[r][l]){

            searchSize(r,l+1);

        }

        return 0;

    }



}