[배열] 봉우리 .java

설명

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

 

내 풀이 

int[] dx = {-1, 0, 1, 0};int[] dy = {0, 1, 0, -1};
-> 현재 위치를 기준으로 순서대로 상,우,하,좌의 시계 방향으로 탐색

 

1. 입력받은 2차원 배열을 0으로 이루어진 행과 열을 하나씩 추가하여 n+1 * n*1의 이차원배열 생성

2. 이중 for문으로 각각의 숫자에 접근하여 각 숫자마다 인접한 상하좌우의 원소들과 비교

-> 새로운 위치를 설정할 때, 인덱스가 0보다 크고 n+1보단 작아야한다

3. 만약 인접한 4개의 숫자 중 하나라도 현재 위치한 수보다 크거나 같으면 봉우리가 될 수 없기에 find 변수를 두어 검사

-> 봉우리가 아니면 바로 for문 나가기

4. 인접한 4개의 숫자를 다 검사한 뒤에도 find가 참이면 봉우리이기 때문에 정답 증가

 

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[][] arr = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
		//위 -> 오 -> 아래 -> 왼의 순서로 탐색
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        int answer = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                boolean find = true;
                //상하좌우 확인
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if (nx > 0 && nx < n+1 && ny > 0 && ny < n+1) {
                        if (arr[i][j] <= arr[nx][ny]) {
                            find = false;
                            break;}
                    }
                }
                
                if (find) answer++;
            }
            
        }
        
        System.out.println(answer);
    }
}

 

 

다른 풀이

따로 0으로 이뤄진 배열을 감싸지 않고 입력받은 원소로만 이차원 배열을 구성하여 푼 코드이다

이때, 인접한 위치 인덱스 범위는 0보다 크거나 같고 n보다 작아야 한다

 

import java.util.Scanner;

public 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){
                        if(arr[nx][ny] >= arr[i][j]){
                            flag = false;
                            break;
                        }
                    }
                }
                if(flag) answer++;
            }

        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        System.out.print(T.solution(n,arr));

    }
}