[알골90제] 47번 - 봉우리 (2차원 배열 탐색)

* 문제를 읽고 난 후

 

- N값을 받은 다음에 정말로 N*N의 2차원 벡터를 만들어야 하나

- 2차원 벡터를 만든다면 상하좌우에 있는 숫자는 어떤 식으로 계산해서 그 자리의 값을 알아낼 것인가

- 반복문을 이용해서 상하좌우 좌표값을 현재 자리 기준에서 연산하여 구하면 되나

- 어떤 알고리즘을 풀어서 해결해야 할지 감도 안 옴

 

 

* 풀이 방법

 

1) 전역 변수로 2차원 배열을 잡으면 모두 0으로 채워진다.

2) 입력받는 숫자 값을 (1.1)부터 넣기 시작한다.

3) 입력을 받았으면, 1행 1열부터 n, n열까지 탐색하는 것이다.

4) 2중 for문이 돌면서 각자가 봉우리 인지 확인해야 한다.

5) i행 j열에 왔다면? 상하좌우를 어떻게 볼 것인가.

6)  현재 a[i][j]

a[i-1][j] 상

a[i][j+1] 우

a[i+1][j] 하

a[i][j-1] 좌

현재 a[i][j] 기준에서 네 방향을 확인해야 한다.

if를 해서 짜기도 하지만,

 

=> 1차원 방향 배열 2개를 만든다. 이걸로 4방향을 탐색한다.

dx[4] = {-1, 0, 1, 0} 선언

dy[4] = {0, 1, 0, -1} 선언

 

a[i+dx[k]] [j+dy[k]] 라는 k for문을 하나 더 돌려야 한다.

상은 -1 + 0 우 0 + 1 하 1+0 좌 0 + (-1) 이런 식으로 보는 건데..

 

a[i-1][j] 상 a[i][j+1] 우 a[i+1][j] 하 a[i][j-1] 좌

dx[4] = {-1, 0, 1, 0} 선언 dy[4] = {0, 1, 0, -1} 선언   k for문 0부터 <4 까지 도는중.. a[i+dx[k]] [j+dy[k]]    ->k == 0 a[i+(-1)][j+0] . . .

왼쪽 -> 오른쪽으로 만들어서 상하좌우를 계산할 수도 있다. 

 

* 코드짜기

// 47번 - 봉우리
// 현재위치 기준 상하좌우가 나보다 모두 작을때 봉우리가 됨
// 봉우리의 개수는?

#define _CRT_SECURE_NO_WARNINGS
#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 };

int main() {

	freopen("input.txt", "rt", stdin);
	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]);
		}
	}
	
    //3중 for문으로 상하좌우 확인
    //k for문 안에 조건절과 flag사용하여 봉우리가 아니면 1 하고 for문 break
    //봉우리가 맞으면 (즉, flag가 계속 1이면) 개수 ++
    
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			flag=0;
			for (k = 0; k < 4; k++) {
				if (a[i + dx[k]][j + dy[k]] >= a[i][j]) {
					flag = 1; //현재위치보다 상하좌우에 같거나 큰게 있으면
					break; //봉우리가 아니기 때문에 더 볼필요 X
				}
			}
            //한자리마다 확인하는 것이기 때문에 그 자리에 k for문으로  상하좌우 확인했으면
            //해당자리 봉우리 맞으면 카운트++한다
			if (flag == 0) cnt++;
		}
	}

	printf("%d\n", cnt);
	return 0;
}

 

* 키워드:

 

- 전역변수 선언하여 미리 배열 0으로 초기화 해놓음

- for문으로 배열 선언할때 1,1 부터 시작해서 넣음

- k for문으로 2차원배열의 상하좌우를 확인해야하기 때문에 3중 for문으로 들어감

- 3중 for문 안에서 상하좌우 위치가 현재의 a[i][j]의 값보다 작은지 확인하기 위해서는

a[i-1][j]   a[i][j+1]  a[i+1][j]  a[i][j-1] 를 확인해야 하는데. . 

각각 따로 하기보다

dx[4]= {-1, 0 1, 0}

dy[4]= {0, 1, 0, -1} 을 선언하여 이것을 for문 0~4까지 각 배열자리를 돌게하고

a[i + dx[k]][j + dy[k]] 로 상하좌우 확인하는 것이 훨씬 효율적이다.

- k for문이 끝나면, 해당 좌표에서 상하좌우 확인이 끝난 것이기에 봉우리가 맞는지 ++해서 맞춘다.

 

 

 

* 이 게시물은 개인 공부를 위해 쓰인 것입니다.