[Inflearn] 봉우리

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역

     - 격자의 가장자리는 0으로 초기화 되었다고 가정

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. N = 5,

     0 0 0 0 0 0 0

     0 5 3 7 2 3 0

     0 3 7 1 6 1 0

     0 7 2 5 3 4 0

     0 4 3 6 4 1 0

     0 8 7 3 5 2 0

     0 0 0 0 0 0 0

     격자의 가장자리는 0으로 초기화 되었다고 가정하자.

     일단 격자의 모든 수를 확인한다고 생각해보면 N = 5 일 때, 총 25 개의 격자를 확인해야 한다.

     최대 N 은 50 개일 때, 2500 개의 격자는 1초 안에 해결이 가능하니 걱정이 없군!

     가장자리를 고려해서 x 좌표가 0 or N-1 일 경우와, y 좌표가 0 or N-1 일 경우는 따로 처리해주어야 할 것 같다.

     우선 상하좌우 숫자들보다 커야 봉우리가 될 수 있으므로 

     (3, 3) 격자를 예로 먼저 들어보면

     상 : (3, 2)

     하 : (3, 4)

     좌 : (2, 3)

     우 : (4, 3)

     의 격자들과 비교를 해보아야 한다.

     식으로 표현해보면 (x, y) 가 들어왔을 때

     if( a[x][y] > a[x][y-1] && a[x][y] > a[x][y+1] && a[x][y] > a[x-1][y] && a[x][y] > a[x+1][y])

    를 만족해야 한다.

    단, 가장자리를 따로 처리해주어야 할 것 같은데.. 차라리 가장자리를 0으로 초기화해두고 시작하는 방법도 나쁘지 않을 것 같다.

    어차피 (1, 1) 부터 (n, n) 까지 탐색하는 것이라면 이렇게 하는게 더 보기도 쉬울테니..

 

    그럼 이 과정을 코드로 옮겨보자!

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int grid[52][52];
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i, j, cnt = 0;
 
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%d", &grid[i][j]);
        }
    }
 
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (grid[i][j] > grid[i][j - 1] && grid[i][j] > grid[i][j + 1] &&
                grid[i][j] > grid[i - 1][j] && grid[i][j] > grid[i + 1][j])
                cnt++;
        }
    }
 
    printf("%d\n", cnt);
 
    return 0;
}

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int map[51][51];
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};
 
int main(){
    int n, i, j, k, flag, cnt=0;
 
    scanf("%d", &n);
 
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            scanf("%d", &map[i][j]);
        }
    }
 
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            flag=0;
 
            for(k=0; k<4; k++){
                if(map[i+dx[k]][j+dy[k]]>=map[i][j]){
                    flag=1;
 
                    break;
                }
            }
 
            if(flag==0) cnt++;
        }
    }
 
    printf("%d\n", cnt);
        
    return 0;
}

강사님께서는 dx, dy 배열을 따로 두시고 구현하셨다.

#. Result

  - Input --------------------------------------------------------

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

------------------------------------------------------------------

  - Output --------------------------------------------------------

10

------------------------------------------------------------------