카카오프렌즈 컬러링북

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

프로그래머스

Level 2

 

주어진 그림의 색깔 기준으로 구분되는 영역의 갯수, 최대 크기 영역의 넓이를 구해야하는 문제

 

만약 이런 예제가 주어질 경우 m 과 n 은 각각 5로 그리고 색칠이 되지 않은 부분은 0, 나머지는 n으로 주어질 것이다. 

 

행렬로 나타내면 다음과 같이 주어질 것이다. 

위 예시의 경우 영역의 갯수는 6개, 최대 크기의 영역은 7이 될 것이다. 

 

내 풀이의 경우 bfs 를 사용해 함수를 구현했다. 

 

1. 그림의 (0,0) 에서 (m,n) 까지 탐색하며 색깔이 있을 경우

 

2. 현재 위치에서 bfs 로 동서남북을 탐색해 자신과 같은 색일 경우 

 

3. 현재 영역의 넓이를 증가시키며 결과적으로 자신이 도달가능한 같은 색의 영역을 전부 탐색하는 것이다.

 

만약 내 현재 위치가 (2, 2) 일 경우 동서남북을 한 번씩 검사할 경우

(2, 1), (1, 2), (3, 2), (2, 3) 을 검사하게 될 것이고

해당 좌표들의 색깔 정보가 일치할 경우에만 영역의 넓이를 확장하고

다음 탐색 대상으로 추가할 것이다.

 

참고로 나의 경우엔 boolean 방문 처리를 하지 않고 방문한 영역의 색깔 정보를 0으로 바꾸어

다음 탐색 시 대상에서 제외 될 수 있게 처리하였다. boolean 배열 만들면 그만큼 메모리가...

 

import java.util.*;

public class Solution { //카카오프렌즈 컬러링북
    static int[][] map;
    static int max_r;
    static int max_c;
    public int[] solution(int m, int n, int[][] picture) {
        map = new int[m][n];
        max_r = m;
        max_c = n;
        for(int i=0; i<max_r; i++) map[i] = picture[i].clone(); //입력 그림 과 같은 새 그림 생성
        ArrayList<Integer> areaList = new ArrayList<Integer>(); //영역 정보를 담을 동적 배열

        for(int row = 0; row < max_r; row++) {
            for(int col = 0; col < max_c; col++) {
                //2중 반복문으로 전체 그림을 탐색
                if(map[row][col] != 0) { //현재 위치가 색칠이 되어있을 경우
                    areaList.add(bfs(row, col)); //현재 위치부터 bfs 실행
                }
            }
        }

        int[] areaArray = new int[areaList.size()]; //영역 정보를 정적 배열에 새로 생성
        for(int idx = 0; idx < areaArray.length; idx++) areaArray[idx] = areaList.get(idx);
        Arrays.sort(areaArray); //정적 배열 O(nlogn) 으로 오름차순 정렬
        return new int[]{areaList.size(), areaArray[areaArray.length-1]}; //[영역 갯수, 가장 큰 영역의 넓이] 반환
    }
    static int bfs(int r, int c) {
        int result = 0;
        int val = map[r][c]; //최초 색깔정보
        int[] position = {r, c};

        Queue<int[]> queue = new LinkedList<int[]>(); //bfs 간 사용할 탐색 예정 좌표 큐
        queue.add(position); //현재 위치 큐에 넣음
        map[r][c] = 0; //현재 위치는 탐색한 것으로 가정하고 색 정보 지움 -> 방문 처리

        while(!queue.isEmpty()) { //좌표 큐에 방문해야할 좌표가 없을 때 까지 반복
            result++; //영역 넓이 +1
            int[] temp_position = queue.poll(); //0번째 좌표 get+remove
            int temp_r = temp_position[0];
            int temp_c = temp_position[1];

            if(temp_r-1>-1 ) { //북쪽 탐색 가능 여부 확인
                if(map[temp_r-1][temp_c] == val) { //북쪽이 같은 색인지 확인
                    int[] temp = {temp_r-1, temp_c};
                    map[temp[0]][temp[1]] = 0; //북쪽 색깔정보 초기화
                    queue.add(temp); //북쪽 이동 후 bfs 탐색 예약
                }
            }

            if(temp_r+1< max_r) { //남쪽 탐색 가능 여부 확인
                if(map[temp_r+1][temp_c] == val) {
                    int[] temp = {temp_r+1, temp_c};
                    map[temp[0]][temp[1]] = 0;
                    queue.add(temp);
                }
            }

            if(temp_c-1>-1 ) { //서쪽 탐색 가능 여부 확인
                if(map[temp_r][temp_c-1] == val) {
                    int[] temp = {temp_r, temp_c-1};
                    map[temp[0]][temp[1]] = 0;
                    queue.add(temp);
                }
            }

            if(temp_c+1<max_c ) { //동쪽 탐색 가능 여부 확인
                if(map[temp_r][temp_c+1] == val) {
                    int[] temp = {temp_r, temp_c+1};
                    map[temp[0]][temp[1]] = 0;
                    queue.add(temp);
                }
            }
        }

        return result; //bfs 종료 후 최종 영역 넓이 반환
    }
}