[프로그래머스] 2017 카카오코드 예선 카카오프렌즈 컬러링북(Java)

 

🔥2022.05.30

 

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

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

 

> 문제 보기

카카오 프렌즈 컬러링북

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

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

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

입력 형식

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

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

출력 형식

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

예제 입출력

mnpictureanswer

6

4

[[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]

[4, 5]

예제에 대한 설명

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

 

 

---

 

🔥 [로직]

내가 문제를 잘 이해를 못하는 타입인건지.. 사실 주어진 문제를 해석하는데 시간이 좀 걸렸다. 

영역에 대한 확실한 정의를 모르겠달까ㅠㅠ  

 

그림을 그려서 설명하자면 

 

예제 입출력 설명

예제에서 주어진 문제를 그려보면 이런 그림이 나온다. 여기서 0은 무시하고 ! 숫자끼리 붙어있으면 연결해주면 된다. 

연결된 덩어리가 영역이라는 개념이다.

 

문제에서는 덩어리의 개수를 numberOfArea로, 가장 큰 덩어리의 사이즈를 maxSizeOfOneArea라는 변수에 담아 리턴하라는 것이다 ㅎㅎ 문제부터 참 .. 빡세다.

 

내 눈은 쉽다는데 이걸 컴퓨터한테 어떻게 이해시켜야 하는건가.. 한참을 그림 그려보고 고민했던 것 같다.

 

[ 재귀함수 구현 ]

내가 선택한 방식은 재귀! (x,y)번째에 있는 값과 같은 영역을 찾는다 하면 각각 상하좌우에 있는 (x+1,y), (x-1,y), (x, y+1), (y, y-1)을 탐색하고 이미 탐색한 위치는 다시는 탐색할 수 없게 체크해준당

 

이 탐색을 위해 구현한 함수가 sizeOfArea다. 

 

해당 위치의 값이 의미없는 값이 아닌경우, 해당 함수를 재귀호출해 인접한 위치의 값까지 불러온다. 리턴값은 여태까지 찾은 인접한 영역의 개수가 된다. 이 위치의 값은 더이상 체크하지 못하도록 0으로 만들어준다.

 

의미없는 값의 기준은 (1) 인덱스를 벗어난 경우(0보다 작거나, m또는 n의 값을 넘어선 경우) (2) 인접한 영역과 다른값을 가진 경우 (3) 0인경우이다. 이 경우에 해당한다면 0을 리턴한다.

 

 

이렇게 sizeOfArea함수를 구현하고 for문을 통해 영역의 크기를 각각 받아온다. 

리턴값이 0보다 큰 경우는 새로운 영역을 찾았다는 뜻이기에 numberOfArea증가, 기존의 max값보다 더 큰 값인 경우 max값을 갱신해준다. 

 

🔥 [최종 코드]

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 1;
        
        int[][] tmp = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                tmp[i][j] = picture[i][j];
            }
        }
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int result = sizeOfArea(tmp, tmp[i][j], i, j);
                if(result == 0) {
                    continue;
                } else {
                    numberOfArea++;
                    if(result > maxSizeOfOneArea) {
                        maxSizeOfOneArea = result;
                    }
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        
        return answer;
    }
    
    public int sizeOfArea(int[][] picture, int num, int x, int y) {
        
        if(x >= picture.length || y >= picture[0].length || x < 0 || y < 0 || (picture[x][y] == 0) || (picture[x][y] != num)) 
            return 0;
        picture[x][y] = 0;
        return 1 
            + sizeOfArea(picture, num, x+1, y) 
            + sizeOfArea(picture, num, x-1, y) 
            + sizeOfArea(picture, num, x, y+1) 
            + sizeOfArea(picture, num, x, y-1);
    }
    
}

 

🔥 [소감]

picture 2차원 배열 그대로 사용하면 안된다는거... 복사해서 사용해야한다는거.. 왜 아무도 나한테 말 안해줬어?

---

부족한 점 피드백 주시면 앞으로의 포스팅에 반영하겠습니다! 봐주셔서 정말 감사합니다 :)
-budtree