[알고리즘 문제풀이] 프로그래머스 카카오프렌즈 컬러링북

오늘도 프로그래머스에서 문제를 풀었다 문제 원문은 여기서 확인하세요 !

주의사항 😤

문제에 조건이 잘 명시되어 있지 않아서 문제가 발생한 부분이 있어서 먼저 언급하고 넘어가려고 한다. 혹시 진짜 잘 푼 것 같은데 통과가 안되시는 분들은 이거 확인해보세요 !

문제에 입력으로 주어지는 int[][] picture 배열을 그대로 보존하여야 한다. 이것이 조건으로는 나와있지 않은데, 질문을 보면서 발견했다. 나는 탐색하면서 방문 체크를 picture배열에 바로 해주었기에 혹시나하고 picture을 그대로 복사하여 사용하였더니 제출이 되었다.. 이 무슨..

문제 설명

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.

입출력 형식

입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 100
• picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
• picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

입출력 예

예제로 주어진 그림은 총 4개의 영역으로 구성되어 있으며, 왼쪽 위의 영역과 오른쪽의 영역은 모두 1로 구성되어 있지만 상하좌우로 이어져있지 않으므로 다른 영역이다. 가장 넓은 영역은 왼쪽 위 1이 차지하는 영역으로 총 5칸이다.

풀이 방법

이어진 영역의 크기들을 구해서 리스트에 저장해준 후 리스트의 크기와 정렬을 통해 가장 큰 값을 반환해주었다.

이어진 영역의 크기를 구하는 것은 BFS를 이용하였다. 그림 배열을 [0,0]부터 반복문을 통해 0이면 탐색을 시작하지 않고 0이 아니라면 그 점을 기준으로 탐색을 시작하였다.

탐색 과정은 먼저 탐색 시작 기준점의 숫자를 저장하고, 탐색 시작 기준점을 큐에 넣어주었다. 이제 큐가 텅 빌 때까지 반복하며, 큐에 제일 먼저 들어온 점에서 사방으로 이동하며 같은 숫자로 이루어졌다면 큐에 삽입해주었다. 이 때, 큐에 삽입한다는 것은 방문한다는 것이므로 중복 방문하지 않도록 0으로 바꾸어주었다. 이 과정에서 큐에서 값을 꺼낼때마다 카운팅을 하며 영역의 크기를 측정하였다.

탐색이 완료되면 그 기준점으로부터 이어진 영역에 대한 탐색은 완료된 것이고, 그림 배열 반복문을 마저 이어가면서 아직 탐색하지 않은 영역을 다시 발견하면 위의 탐색을 시작하는 방식으로 구현하였다.

코드

import java.util.*;
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    
    public int bfs(int[] start, int[][] picture, int m, int n){
        int count = 0;
        Queue<int[]> queue = new LinkedList<>();
        int color = picture[start[0]][start[1]];
        picture[start[0]][start[1]] = 0;
        queue.add(start);
        int[] current;
        int x, y;
        while(!queue.isEmpty()){
            current = queue.poll();
            count++;
            for(int i=0; i<4; i++){
                x = current[0]+dx[i];
                y = current[1]+dy[i];
                if(x<0 || x>=m || y<0 || y>=n) continue;
                if(picture[x][y]==color){
                    picture[x][y] = 0;
                    queue.add(new int[]{x, y});
                } 
            }
        }
        return count;
    }
    
    public int[] solution(int m, int n, int[][] picture) {
    	// 주의 사항대로 원본 유지를 위한 복사 과정
        int [][]pic = new int[m][n];
        for (int x = 0; x < picture.length; x++) {
            for (int y = 0; y < picture[x].length; y++) {
                pic[x][y] = picture[x][y];
            }
        }
        
        ArrayList<Integer> areas = new ArrayList<>();
        for(int i=0; i<pic.length; i++){
            for(int j=0; j<pic[i].length; j++){
                if(pic[i][j] == 0) continue;
                areas.add(bfs(new int[]{i, j}, pic, m, n));
            }
        }
        Collections.sort(areas);
        return new int[]{areas.size(), areas.get(areas.size()-1)};
    }
}