2017 카카오코드 예선 카카오프렌즈 컬러링북

문제

스크린샷 2020-03-19 오후 10 27 06

class Solution {
    static boolean[][] visited;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int row;
    static int col;
    static int curMax = 1;

    public void dfs(int x, int y, int value, int[][] picture){

        visited[x][y] = true;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >=0 && ny >=0 && nx<row && ny<col && !visited[nx][ny] && picture[nx][ny] == value){
                curMax +=1;
                dfs(nx,ny,value,picture);
            }
        }
    }

  public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        visited = new boolean[101][101];

        row = m;
        col = n;

        int[] answer = new int[2];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(picture[i][j] != 0 && !visited[i][j]){
                    numberOfArea++;
                    dfs(i,j,picture[i][j],picture);
                    maxSizeOfOneArea = Math.max(curMax,maxSizeOfOneArea);
                    curMax = 1;
                }
            }
        }

        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

        return answer;
  }
}

전형적인 DFS 문제이다.

DFS,BFS 문제는 이미 삼성으로 단련되었기 때문에 비교적 쉽게 풀 수 있었다.

다만 프로그래머스 컴파일러의 한 가지 문제점이 있는데,

전역으로 선언할 때 메모리 할당을 하면 틀렸다고 나오고, 함수 내에서 메모리 할당을 하면 답이 맞게 나오는 아주 황당한 오류가 존재한다.

스크린샷 2020-03-19 오후 10 28 53

나도 다 풀고나서 틀렸다고 나오길래 질답게시판을 봤더니 나같은 사람이 꽤 있나보다.

덕분에 도움을 받았다.

스크린샷 2020-03-19 오후 10 29 37

(처음에 맞췄을 때 찍어놓을걸)



© 2022. by minkuk

Powered by minkuk