Programmers - 카카오프렌즈 컬러링북(JAVA)

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

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

 

풀이

* 0은 색칠하지 않은 영역, 영역 탐색 대상에서 제외

1. 이차원 배열 각 요소마다 탐색

    - 이미 탐색했거나(visit[y][x]==true) 해당 위치의 값이 0이면 continue

    - 외의 경우에는 현재 위치가 이전까지 찾은 영역과 다른 새로운 영역이기 때문에 영역 갯수+1, 영역 사이즈 구하기(2로 이동)

2. 상하좌우 인접한 칸을 계속해서 확인

    - 이미 탐색한 위치가 아니면서 기준 위치의 값과 현재 탐색의 위치의 값이 같은지 확인 -> 같은 영역

    - visit[ny][nx]=true로 이미 탐색한 위치를 구분, 영역의 사이즈+1

    - 더이상 탐색할 수 있는 위치가 없을 때까지 확인 후 3으로 이동

3. 현재 탐색한 영역의 사이즈과 최대 영역사이즈를 비교/갱신

 

 

import java.util.*;
 
class Solution {
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    static int M,N;
    boolean[][] visit = new boolean[101][101];
    
    static class Pair{
        public int y;
        public int x;
        
        Pair(int y, int x){
            this.y=y;
            this.x=x;
        }
    }
    
    public int[] solution(int m, int n, int[][] picture) {
        M=m;
        N=n;
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        
        // picture 하나씩 탐색
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                // 이미 방문했거나 배열값이 0이면 pass
                if(visit[i][j]|| picture[i][j]==0)continue;
                // 영역 갯수 +1 
                numberOfArea++;
                // 영역의 사이즈 구하기
                int size = bfs(picture,  i,j);
                if(size>maxSizeOfOneArea)
                    maxSizeOfOneArea=size;
            }
        }
        
        int[] answer = new int[2];
        answer[0]=numberOfArea;
        answer[1]=maxSizeOfOneArea;
        return answer;
    }
    
    public int bfs(int[][] picture, int i, int j){
        int value=picture[i][j];
        int size=1;
        visit[i][j]=true;
        LinkedList<Pair> q= new LinkedList<>();
        q.add(new Pair(i,j));
        
        while(!q.isEmpty()){
            Pair now= q.poll();
            
            for(int d=0;d<4;d++){
                int ny=now.y+dy[d];
                int nx=now.x+dx[d];
                // 격자 범위 내인지
                if(ny<0||nx<0||ny>=M||nx>=N)continue;
                // 방문한 위치이면 pass
                if(visit[ny][nx])continue;
                // 기준 위치와 현재 탐색 위치의 배열값이 같은지
                if(picture[now.y][now.x]!=picture[ny][nx])continue;
                visit[ny][nx]=true;
                // 영역 사이즈 +1, 탐색 요소 추가
                size++;
                q.add(new Pair(ny,nx));
            }
        }
        
        return size;
    }
}