프로그래머스 - 카카오프렌즈 컬러링북(Java, 2017카카오)

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

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

풀이

• 전체 그래프에서 탐색할 영역 중 영역 0(배경색)을 제외한다
• 그래프 중 방문하지 않은 곳을 찾아서 그곳을 시작점으로 같은 색으로만 DFS 탐색을 한다.
• DFS 탐색을 하면서 영역의 수를 count하고, count한 영역이 최대영역 크기보다 크면 갱신한다.
• DFS 가 끝나면 전체 그래프 중에서 다시 탐색하지 않은 곳을 찾아서 DFS 탐색을 호출한다.
• DFS 를 호출한 수를 계산하면 총 몇 개의 영역이 있었는지 알 수 있다.
• 영역 개수와 최대 영역 크기를 반환한다. 

import java.util.*;

class Point{
    int x;
    int y;
    public Point(int x, int y){this.x =x; this.y=y;}
}

class Solution {
    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;
    
    // 방문하지 않은 곳 반환
    public Point getNotVisit(int m, int n, int[][] visit){
        for(int i =0; i<m;i++){
            for(int j=0;j<n;j++){
                if(visit[i][j] == 0){
                    Point now = new Point(i,j);
                    return now;
                }
            }
        }
        // 방문 다했을 시 -1,-1 반환
        Point fin = new Point(-1,-1);
        return fin;
    }
    
    public void DFS(int m, int n, int[][] picture, int[][] visit, Point start){
        // variable
        int val = picture[start.x][start.y]; // 같은 색깔 영역
        int[] dx = {-1, 1, 0, 0}; // UDRL
        int[] dy = {0, 0, 1, -1}; // UDRL
        Stack<Point> stack = new Stack<>();
        
        stack.push(start);
        int cnt = 0;
        
        // 빌 떄 까지 반복
        while(!stack.isEmpty()){
            Point now = stack.pop();
            if(visit[now.x][now.y] == 0){
                visit[now.x][now.y] = 1; // 방문
                cnt++;
            }
            // 4방향 방문
            for(int i=0; i<4;i++){
                int nx = now.x+dx[i];
                int ny = now.y+dy[i];
                
                // 범위 안이고 같은 색깔이고 방문하지 않은 곳
                if(nx>=0 && nx< m && ny >=0 && ny <n && picture[nx][ny] == val && visit[nx][ny] == 0){
                    stack.push(new Point(nx,ny));
                }
            }
        }
        // 최대값 갱신, 영역 수 증가
        maxSizeOfOneArea = Math.max(cnt, maxSizeOfOneArea);
        numberOfArea++;
    }
    
    public int[] solution(int m, int n, int[][] picture) {

        int[][] visit = new int[m][n];
        
        // 0 값 처리
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(picture[i][j]==0)
                    visit[i][j]=1; // 방문처리
        
        // picture에 대해 완전탐색 돌기
        while(true){
            Point start = getNotVisit(m,n,visit);
            // 방문완료시
            if(start.x == -1 && start.y == -1){break;}
            
            // 그 외 방문
            DFS(m, n, picture, visit, start);
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}