알고리즘 풀이 - 프로그래머스(카카오프렌즈 컬러링북(Lv 2), BFS)

 

관련글

 

그래프 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

여러 장의 그림을 난이도 순으로 컬러링 북에 넣을 때, 난이도를 영역의 수로 정하였다면 그림의 영역의 수와 가장 큰 영역의 넓이가 얼마인지 계산하는 문제

 

 

2. 풀이

 

예시로 주어진 그림의 영역의 수 및 넓이를 알아보자.
(영역은 숫자가 0이면 칠해지지 않은 것이며, 나머지는 그려진 것이다.)

 

위에서 색칠된 부분만 그림이므로, 영역은 총 4개이고 그 중 넓이가 가장 넓은 것은 5임을 알 수 있다.

 

BFS를 통해 인접 같은 숫자 그림을 칠하고, 그 영역을 계산하는 방식으로 해결하는 간단한 문제이다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.util.*;
class Solution {
    private boolean[][] bool;
    private int[] dy = {-1, 0, 1, 0};
    private int[] dx = {0, -1, 0, 1};
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        bool = new boolean[m][n];
        for(int i=0; i < m; i++){
            for(int j=0; j < n; j++){
                if(!bool[i][j] && picture[i][j] != 0){  // 이미 칠한 영역이 아니며, 0이 아닌 경우
                    int area = bfs(m, n, i, j, picture);
                    numberOfArea++; // 영역 추가
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, area); // 영역 크기 갱신
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    // BFS를 통해 같은 인접한 같은 영역을 모두 동일하게 칠하고 방문 완료 처리한다.
    private int bfs(int m, int n, int i, int j, int[][] picture){
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(i, j, picture[i][j])); // 현재 위치, 그림 숫자를 넣는다.
        bool[i][j] = true;
        
        int area = 1;
        while(!q.isEmpty()){
            Pos c = q.poll();
            for(int k=0; k < 4; k++){
                int ny = c.y + dy[k];
                int nx = c.x + dx[k];
                if(ny < 0 || ny >=m || nx < 0 || nx >= n || bool[ny][nx]) continue; // 범위를 벗어났거나 이미 방문된 경우 넘어간다.
                if(picture[ny][nx] != c.n) continue; // 다른 숫자면 넘어간다.
                q.add(new Pos(ny, nx, picture[ny][nx]));  // 같은 숫자인 경우 추가
                bool[ny][nx] = true;
                area++;
            }
        }
        return area;
    }
}

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

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.