47. 봉우리

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

5

5 3 7 2 3

3 7 1 6 1

7 2 5 3 4

4 3 6 4 1

8 7 3 5 2

 

출력예제 1 

10

 

풀이 

2차원 배열 탐색 문제

2차원 배열의 한위치에서 상하좌우와 비교해 값이 더 크면 봉우리가 되고 이를 카운팅한다.

 

- 주의해야 할 점

(1) 범위가 n=50까지 들어갈 수 있기 때문에 배열 선언시에는 전역으로 a[51][51]

(2) flag값을 설정해서 상하좌우와 비교했을 때 기준이 되는 값보다 큰 값이 하나라도 나오면 바로 break하는 구문이 필요

 

 

- 생각해야 할 점

(1) 2차원 배열의 한 위치에서 어떻게 하면 상하좌우에 있는 값들과 비교할 수 있을지 생각하는 것이 중요

=> 처음에는 if문으로 모든 방향과 비교해야겠다고 생각했는데 이는 비효율적일 것이라는 생각이 듬

=> 행과 열의 이동을 배열로 담음

	a[i-1][j] :  -1, 0
a[i][j-1] : 0, -1	기준값 a[i][j]	a[i][j+1]: 0, 1
	a[i+1][j] : 1, 0

시계 방향으로 dx는 [-1, 0, 1, 0], dy는 [0, 1, 0, -1]

 

(2) for문 두개로 배열의 모든 값들을 검사하고 그 안에서 또 다른 for문으로 4번씩 상하좌우와 비교해야 한다. 코드에서 for(k=0;k<4;k++)

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int a[51][51];
int dx[4]={-1, 0, 1, 0}; //시계 방향 행 변경
int dy[4]={0, 1, 0, -1}; //시계 방향 열 변경


// 47. 봉우리

int main() {
    int n, i, k, j, cnt=0, flag;
    scanf("%d", &n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            flag=0;
            for(k=0;k<4;k++){
                if(a[i][j]<=a[i+dx[k]][j+dy[k]]){
                    flag=1;
                    break;
                }
            }
            if(!flag) cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}