자바 알고리즘 문제 풀이 입문. 섹션2. Array(1, 2차원 배열) : 봉우리

 

https://hyejin.tistory.com/1217

자바 알고리즘 문제 풀이 입문. 섹션2. Array(1, 2차원 배열) : 격자판 최대합

-> 이전 문제 풀이 

 

 

 

10. 봉우리 

 

설명

지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다.

각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.

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

만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

 

입력

첫 줄에 자연수 N이 주어진다.(2<=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

 

 

문제 풀이 1

public int solution(int n, int[][] arr)
{
   int answer = 0;
   int[][] tmp = new int[n + 2][n + 2];
   
   for (int i = 0; i < tmp.length; i++)
   {
      for (int j = 0; j < tmp[i].length; j++)
      {
         if (i == 0 || j == 0 || i == tmp.length - 1 || j == tmp.length - 1) {
            tmp[i][j] = 0;
         }else {
            tmp[i][j] = arr[i - 1][j - 1];
         }
      }
   }
   
   for (int i = 0; i < tmp.length; i++)
   {
      for (int j = 0; j < tmp[i].length; j++)
      {
         if (!(i == 0 || j == 0 || i == tmp.length - 1 || j == tmp.length - 1))
         {
            if ((tmp[i][j] > tmp[i][j - 1]) && (tmp[i][j] > tmp[i - 1][j]) && (tmp[i][j] > tmp[i + 1][j]) && (tmp[i][j] > tmp[i][j + 1]))
            {
               answer++;
            }
         }
      }
   }
   
   return answer;
}

👩‍💻 : 나는.. 우선 문제에서 제시한 그림처럼 tmp 배열을 하나 더 만들었다. 끝은 모두 0으로 초기화해주고, 그 안에 값을 arr의 배열 값을 그대로 넣어줬다. 

 

그 다음.. 끝의 부분들이 아니라면

if (!(i == 0 || j == 0 || i == tmp.length - 1 || j == tmp.length - 1))

tmp[i][j]의 값을 동서남북으로 비교해서 tmp[i][j]값이 가장 크다면 answer에 +1 하도록 했다..! 

 

-> 이 문제는 if 문으로 처리했지만.. 만약 동서남북이 아니라 정사각형으로 비교하라.했으면 8번의 비교를 했어야 하는데 

굉장히 코드도 더럽고... 별로일 것이다.. 

 

 

 

문제 풀이 2

int[] dx = { -1, 0, 1, 0 };
int[] dy = { 0, 1, 0, -1 };
public int solution2(int n, int[][] arr)
{
   int answer = 0;
   
   for (int i = 0; i < n; i++)
   {
      for (int j = 0; j < n; j++)
      {
         boolean flag = true;
         for (int k = 0; k < 4; k++)
         {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if ( nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] > arr[i][j]) {
               flag = false;
               break;
            }
         }
         if (flag)
            answer++;
      }
   }
   
   return answer;
}

👾 : 그래서 강사님은 

int[] dx = { -1, 0, 1, 0 };
int[] dy = { 0, 1, 0, -1 };

-> 동서남북에 각각 배열을 만들어두고, 

3중 for문을 돌게 했다. k = 0  i + dx[0],  j + dy[0] 를 하면 '북' 값에 해당하고, k = 1 -> i + dx[1], j + dy[1] 은 '동'값에 해당한다. 

 

이때 

int nx = i + dx[k];
int ny = j + dy[k];

nx, ny 값이 0보다 크거나 같아야 하고, n 보다는 작아야 비교할 수 있다. 

 

따라서 arr[i][j]의 값이 arr[i +dx[k]][j+dy[k]] 보다 작다는 말은 봉우리가 될 수 없다는 것이므로 boolean flag 값을 false로 지정해준다. 그 다음 더이상 비교할 필요 없으니 break 해주고,, 

 

비교 후 flag 값이 true이면 answer +1 해준다.