[알고리즘] 프로그래머스 카카오프렌즈 컬러링북 Java(자바)

- 문제

 

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

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

- 코드 설명

 

문제를 다 풀고 테스트 코드는 맞는데 제출하면 틀려서 질문하기를 통해 테스트케이스 하나를 추가했다.

 

3,3

[[0, 1, 0], [1, 1, 0], [0, 0, 0]]

[1, 3]

 

하지만 원인은 오타였....

 

모든 좌표를 탐색하여 같은 그룹을 찾는다.

해당 좌표와 같은 색을 탐색하기 위해선 다른 그룹에 속한적이 없고(visited[][] == false) 처음 기준으로 잡았던 타일과 색이 같아야 한다.

이를 기준으로 상,하,좌,우를 조건에 맞게 탐색하여 

그룹으로 나누어진 부분(numberOfArea)과 그룹 중에 타일의 수가 가장 많은것(maxSizeOfArea)을 찾아내면 된다.

import java.util.*;

class Solution {
    static int[] direction;
    static boolean[][] visited;
    static int M,N;
    static int[][] pic;
    public int[] solution(int m, int n, int[][] picture) {
        pic = picture.clone();
        M = m;
        N = n;
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        visited = new boolean[m][n];
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(picture[i][j] != 0 && visited[i][j] == false){
                    visited[i][j]= true;
                    numberOfArea++;
                    maxSizeOfOneArea = Math.max(sol(picture[i][j] ,j, i),maxSizeOfOneArea);
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    static int sol(int color, int x, int y){
        int max = 1;
        visited[y][x] = true;
        //상
        if(y-1 >= 0 && pic[y-1][x] == color && visited[y-1][x] == false){
            max += sol(color, x, y-1);
        }
        //하
         if(y + 1 < M && pic[y+1][x] == color && visited[y+1][x] == false){
            max += sol(color, x, y+1);
        }
        
        //좌
        if(x-1 >= 0 && pic[y][x-1] == color && visited[y][x-1] == false){
            max += sol(color, x-1, y);
        }
        //우
        if(x+1 < N && pic[y][x+1] == color && visited[y][x+1] == false){
            System.out.println("right");
            max += sol(color, x+1, y);
        }
        
        return max;
    }
}

 

- 결과