[프로그래머스] 카카오프렌즈 컬러링북 (재귀)

문제링크

코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스

 

그래프 조건에서 == 1 일 때와, != 0 인 경우의 차이점은 뭘까.

무조건 == 1로만 생각하고 풀었더니 성공하지 못했다.

 

백준2667 단지번호 붙이기

[백준] 2667번 단지번호붙이기 Java (DFS, BFS)

위 문제와 상당히 비슷하다고 생각하여 똑같이 풀이를 하였는데, 위 조건 때문에 실패 요인이었다.

월요일에 출근해서 물어봐야지..

 

문제 풀이

//link : https://programmers.co.kr/learn/courses/30/lessons/1829
//ref : https://twpower.github.io/151-bfs-dfs-basic-problem
public class KakaoColoringBook {

    private static int[] dx = {0,0,1,-1};
    private static int[] dy = {1,-1,0,0};

    private static boolean[][] visited = new boolean[100][100];
    private static int[][] map = new int[100][100];

    private static int count = 0;

    private static ArrayList<Integer> list = new ArrayList<>();

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

        map = new int[m][n];
        visited = new boolean[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                //0이 아니고 방문하지 않았다면
                if(picture[i][j] != 0 && !visited[i][j]){
                    count = 0;
                    numberOfArea++; // 방문 구역 ++
                    dfs(i,j,picture,m,n);
                    //한 구역을 탐색이 끝나면 크기 영역 크기 비교
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, count);
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

        return answer;
    }

    private void dfs(int x, int y, int[][] picture, int m, int n) {
        int now = picture[x][y];
        visited[x][y] = true;
        count++;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && ny >= 0 && nx < m && ny < n){
                if(picture[nx][ny] == now && !visited[nx][ny]){
                    dfs(nx,ny,picture,m,n);
                }
            }
        }
    }

    public static void main(String[] args) {
        KakaoColoringBook k = new KakaoColoringBook();

        int m = 6;
        int 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}};

        System.out.println(Arrays.toString(k.solution(m,n,picture)));
    }
}