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

민지킴·2021년 4월 20일
0

프로그래머스

목록 보기
17/42
post-thumbnail

문제 링크

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

문제 풀이

bfs를 사용하여 접근했다.

칸의 번호가 0보다 크며, 방문하지 않은 경우에는
bfs 탐색을 이용하여 넓이를 구하도록 하였다.
해당 칸의 size를 1로 초기화(이미 최소 한칸은 있다는 뜻이므로) 하였고
bfs를 돌때마다 size를 ++를 해주었으며, bfs끝나고 난후에는 최대면적과 비교하였다.

for(int i=0; i<m; i++){
        	for(int j=0; j<n; j++){
            	if(picture[i][j]>0 && visited[i][j]!=true){
                	size=1;
                    bfs(picture,i,j,m,n);
                    numberOfArea++;
                    if(maxSizeOfOneArea<size){
                    	maxSizeOfOneArea = size;
                    }
                }
            }
        }

코드

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

static class Node{
    	int x;
        int y;
    

      public Node(int x, int y){
          this.x=x;
          this.y=y;
      }
  }
  static Queue<Node> queue = new LinkedList<Node>();
  static boolean [][] visited;
  static int size = 0; //칸의 개수
  
  public int[] solution(int m, int n, int[][] picture) {
        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]!=true){
                	size=1;
                    bfs(picture,i,j,m,n);
                    numberOfArea++;
                    if(maxSizeOfOneArea<size){
                    	maxSizeOfOneArea = size;
                    }
                
                }
            }
        }
      int[] answer = new int[2];
      answer[0] = numberOfArea;
      answer[1] = maxSizeOfOneArea;
      return answer;
  }
   static void bfs(int[][] pic, int x, int y, int m, int n){
        queue.add(new Node(x, y));
        visited[x][y] = true;
        
        while(!queue.isEmpty()){
            Node now = queue.poll();
            
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                
                if(0 <= nx && nx < m && 0 <= ny && ny < n){
                    if(pic[nx][ny] == pic[x][y] && visited[nx][ny] != true){
                        queue.add(new Node(nx, ny));
                        visited[nx][ny] = true;
                        size++; // 지나온 칸의 개수
                    
                    }
                }
            }
        }
    }
  

}
profile
하루하루는 성실하게 인생 전체는 되는대로

0개의 댓글