[프로그래머스 - 카카오] 인형뽑기 - Java

 

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

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

코드를 쓰는데는 그렇게 시간이 오래 걸리지 않았지만

int[][] picture를 long[][] 타입으로 바꾸어야 정확도 테스트를 통과하기 때문에 그걸 몰라 애를 먹었다..

사실 왜 이렇게 바꿔야하는지도 잘 모르겠지만..ㅠ 

• picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.

라고 되어있었기 때문에 picture 원소들은 모두 int범위 내에 존재할텐데.. 호옥시나 아시는 분들은 알려주세요... 호옥시나 이 글을 보게된다면...ㅋㅋㅋ

 

로직

floodfill 문제 풀 때랑 똑같이 풀었다.

int[][] picture를 long[][] 으로 변환 → picture를 순회하면서 0이 아닌 값을 발견하게되면 해당 좌표값을 가지고 너비우선탐색(bfs)을 시작 → 좌표값 기준 위 아래 왼쪽 오른쪽을 보고 좌표값이 가지는 value와 동일하다면 또 다시 해당 좌표값을 가지고 bfs 시작 → ...  → 이런 식으로 재귀호출을 해준다.

 

bfs()를 한 번 호출 할 때마다 한 좌표씩 다루는 것이기 때문에 함수 내부에서 한 번 카운트(영역 면적 하나~) + 재귀호출 결과값(다른 재귀호출에서 카운트된 또 다른 영역의 면적)을 리턴해준다 ( 최종 리턴 값 = 현재 탐색한 영역의 면적).

항상 재귀호출은 설명이 힘들어

 

우리는 최종적으로 answer : [영역 개수, 가장 넓은 영역 면적]을 리턴해줄 것이기 때문에

bfs 탐색이 끝나면 영역이 하나 완성되었으므로 answer[0] +=1

현재 bfs 탐색으로 찾은 영역의 면적이 이전의 면적보다 넓은지 체크하고 넓으면 answer[1] 업데이트!

 

이런 식으로 반복반복~

 

 

코드

import java.util.Arrays;
class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        long[][] pic = convertToLong(m, n, picture);
        return search_start_point(m, n, pic);
    }
    
    public int[] search_start_point(int m, int n, long[][] picture){
        int[] answer = {0, 0};
        for(int i =0; i < m; i++){
            for(int j = 0; j < n; j++){
                 if(picture[i][j] != 0){
                     long area = bfs(m, n, i, j, picture, picture[i][j]);
                     answer[1] = (answer[1] < (int) area) ? (int) area : answer[1];
                     answer[0] += 1;
                 }
            }
        }
        return answer;
    }
    
    public int bfs(int m, int n, int i, int j, long[][] picture, long value){
        picture[i][j] = 0;
        int counter = 0;
        if(0 < i && picture[i-1][j] == value){
            counter += bfs(m, n, i-1, j, picture, value);
        }
        if(i < m - 1 && picture[i+1][j] == value){
            counter += bfs(m, n, i+1, j, picture, value);
        }
        if(0 < j && picture[i][j-1] == value){
            counter += bfs(m, n, i, j-1, picture, value);
        }
        if(j < n - 1 && picture[i][j+1] == value){
            counter += bfs(m, n, i, j+1, picture, value);
        }
        return 1 + counter;
    }
    long[][] convertToLong(int m, int n, int[][] picture){
        
        long[][] converted = new long[m][n];
        for(int i = 0; i< m; i++){
            for(int j =0; j <n; j++){
                converted[i][j] = picture[i][j];
            }
        }
        return converted;
    }
}