5. codeup 2062 : Up 2 문제 해결

이번에는 Up 2라는 문제인데요. 이 문제는 영화 '업'과 관련이 있어 보여서 풀게 되었습니다. 영화 '업'을 제가 되게 재미있게 본 기억이 있어서요 ㅎㅎ;; 

 

문제 설명 입니다.

출처<코드업 사이트>

이차원 배열을 만들어서 탐색하여 같은 숫자가 최대 몇개 연결되어 있는지를 알아봐야 할 것 같습니다.

 

알고리즘 모식도 입니다.

 k=0 부터 9까지 모든 배열을 탐색하면서 k값과 같은 [i][j]에서부터 주변을 재귀함수로 탐색하면서 이어져 있는 부분이 몇개인지를 알 수 있습니다. 그리고 이 이어져 있는 부분의 최댓값을 구하여 출력하면 문제 해결!

#include <stdio.h>

int arr[20][20];  //지붕 배열
int max[10]={0};   //최댓값 저장 배열
int m,n;  //지붕 크기

int pang(int i, int j, int k) {
    if(i < 0 || i >= m || j < 0 || j >= n) {   //배열을 넘어가지 않는지 조건 확인
        return 0;
    }
    if(arr[i][j] == k) {   //주변 탐색
        int cnt = 1;
        arr[i][j] = -1; 
        cnt += pang(i-1, j, k);
        cnt += pang(i+1, j, k);
        cnt += pang(i, j-1, k);
        cnt += pang(i, j+1, k);
        return cnt;
    }
    return 0;
}

int main() {
    scanf("%d %d",&m, &n);   //지붕 크기
    for(int i =0;i<m;i++) {   
        for(int j=0;j<n;j++) {
            scanf("%d",&arr[i][j]);   //지붕배열 입력
        }
    }
    for(int k =0; k<=9;k++) {          //각 층별로 탐색
        for(int i =0;i< m; i++) {
            for(int j=0;j<n;j++){
                if(arr[i][j] ==k){
                    int cnt = pang(i,j,k);   
                    if(cnt>= max[k]){        //카운트한 값이 지금까지의 최댓값보다 크면 교체
                        max[k] = cnt;
                    }
                }
            }
        }
        if (max[k]!= 0){       //카운트 값이 0이 아닌 층만 출력
            printf("%d %d\n",k, max[k]);
        }
    }
}

지금 봤는데 함수 이름이 pang이네요 ㅋㅋ,,  이 문제를 풀기 전에 버블팡이라는 문제를 풀고 있어서 함수 이름이 pang으로 지어놓고 바꾸지를 않았네요. 아무튼 이 코드는 위의 알고리즘처럼 각 층마다 탐색을 진행하여 이어져 있는 부분의 최댓값을 구합니다. 코드가 긴 편이지만 코드를 차근 차근 따라가면 배열과 탐색이 어떻게 이뤄지는지 파악할 수 있을것 같습니다!   

 

문제는 영화와 별로 관련이 없는 것 같았지만 이런 영화 관련문제가 있다는 것이 참 흥미롭네요. 나중에 Up 1 문제도 꼭 풀어봐야겠습니다! 그럼 오늘도 저의 부족한 게시물을 읽어 주셔서 감사합니다! 바이바이