[코딩테스트 / c++] 봉우리, 이차원 배열 활용

문제

지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

▣ 입력설명
첫 줄에 자연수 N이 주어진다.(1<=N<=50)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는 다.

▣ 출력설명
봉우리의 개수를 출력하세요.

 

입력예제 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

 

풀이

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int a[60][60];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int main(){
	
	int n, i, j, k, 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==0) cnt++;
		}
	}
	printf("%d\n", &cnt);
	
	return 0;
}

이차원 배열에 위치별로 각 지역의 높이를 저장하고, 봉우리인지 알기 위해 상하좌우 위치를 확인해야 한다. 

만약 기준되는 위치가 (1,1)일 경우 북쪽으론 (0,1)이고, 동쪽으론 (1,0), 남쪽으로 (2,1), 서쪽으론 (1,2)가 위치하고 있을 것이다. 그럼 a[i][j]에서 북동서남 기준으로 a[i-1][j], a[i][j-1] , a[i+1][j], a[i][j+1] 라는 규칙이 생성된다. 

 

이 규칙을 활용하여 dx, dy배열에 담아 더하면 다음과 같은 공식이 성립되게 된다.

a[i+dx[k]][j+dy[k]]
dx[4]={-1, 0, 1, 0}
dy[4]={0, -1, 0, 1}

 

동서남북 높이가 자신의 높이가 더 크면 봉우리 지역이 아니면 비교를 멈추고, 모두 크지 않으면 카운트를 세면 봉우리의 개수를 구할 수 있다.