봉우리 값 구하기

19 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

지도 정보가 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

해결방법

• 특정 배열 원소의 상,하,좌,우로 연결 되어있는(주변 값 구하기 등 포함) 것을 판단하는 문제

• 특정 배열의 원소의 상,하,좌,우라 함은 원소 기준을 (0,0) 좌표로 보면 상은 (0,-1) 하는 (0,1) 좌는 (-1,0) 우는 (1,0) 만큼 이동한 것이다. 이 것을 기준으로 우리는 행과 열을 이동할 크기 배열을 미리 정의 한다.

  // 시계방향 기준으로 셋트. 
  int[] mx = {0,1,0,-1}
  int[] my = {-1,0,1,0}
  // 12시 : (0,-1)
  // 3시  : (1,0)
  // 6시  : (0,1)
  // 9시  : (-1,0)
  

• 이 배열을 이용하여 이중 for문으로 배열을 돌리며, 각 원소별로 판단을 실시 한다.

코드

import java.util.*;

class Main {
    // 시계방향 판단할 배열 미리 선언 
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};

    public int solution(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;
    }

    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = kb.nextInt();
            }
        }
        System.out.print(T.solution(n, arr));
    }
}