[JAVA/DFS] 프로그래머스 카카오프렌즈 컬러링북

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/1829?language=java 

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

 

2. 풀이

• picture을 돌아다니면서, 방문하지 않은 색깔 영역(picture[i][j] != 0)이 나오면
  • DFS로 해당 색깔의 영역 크기를 구한다.
• 영역의 크기를 구할 때마다, 크기를 비교해 그 중 가장 큰 값을 구한다.

 

3. 코드

 

import java.util.*;

class Solution {
    // 현재 위치(r,c)가 범위 내에 았는지
    public boolean isInRange(int m, int n, int r, int c){
        return (r >= 0 && r < m && c >= 0 && c < n);
    }
    
    // 영역의 크기 구하는 함수
    public int dfs(int m, int n, int r, int c, int[][] picture, boolean[][] visited){
        Queue<int[]> q = new LinkedList<int[]>();
        int size = 1;
        int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};
        
        q.offer(new int[]{r, c});
        
        while(!q.isEmpty()){
            int[] point = q.poll();
            int nowR = point[0];
            int nowC = point[1];
            
            for(int i = 0; i < 4; i++){
                int newR = nowR + next[i][0];
                int newC = nowC + next[i][1];
                if(isInRange(m, n, newR, newC) && picture[newR][newC] == picture[nowR][nowC] && !visited[newR][newC]) {
                    visited[newR][newC] = true;
                    q.offer(new int[]{newR, newC});
                    size++;
                }
            }
        }
    
        return size;
    }
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0; // 영역 개수
        int maxSizeOfOneArea = 0; // 가장 큰 영역 크기
        boolean[][] visited = new boolean[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!visited[i][j] && picture[i][j] != 0){
                    visited[i][j] = true;
                    int now = dfs(m, n, i, j, picture, visited);
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, now);
                    numberOfArea++;
                }
            }
        }
        
        return new int[]{numberOfArea, maxSizeOfOneArea};
    }
}