[Inflearn] 자바 알고리즘 문제풀이 #02-10 10. 봉우리

문제

설명

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

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

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

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

 

입력 

첫 줄에 자연수 N이 주어진다.(2<=N<=50)

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.

 

출력

봉우리의 개수를 출력하세요.

 

 

 

선생님 풀이

import java.util.Scanner;

public class Main2_10 {
    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]; // 위, 오른, 아래, 왼쪽 네 방향의 x, y좌표
                    int ny = j+dy[k];
                    if(nx>=0 && nx<n && ny>=0 && ny<n && arr[nx][ny] >= arr[i][j]) {
                        // 네 방향으로 이동했을 때 좌표가 배열 범위 안에 있어야 하고, 가운데 값보다 작아야 봉우리
                        flag = false; // 네 방향 중 한 방향의 값이 가운데 값보다 클 경우 false
                        break;
                    }
                }
                if(flag) answer++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main2_10 T = new Main2_10();
        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.println(T.Solution(n, arr));
    }
}

 

 

 

결과

 

 

 

알게된 점

위 문제는 이동할 좌표(nx, ny)의 인덱스가 유효한지 (0~n-1 사이에 있는지) 확인해야 하는데

나는 계속 조건문 자체에 arr[i][j] > arr[i-1][j] 이런 식으로 네 방향 적어놓아서 IndexOutOfBoundsException 떴지만 해결할 수 없었다. (테두리에 000000을 추가하지 않는 이상 풀 수 없는 방식)

 

 

특정 좌표에서 근접 좌표들에 접근할 때

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

위의 방향 배열을 만든 후 for(int k=0; k<4; k++) nx = i + dx[k]; ny = j + dy[k]; 식으로 접근한다는 발상에 놀랐다.

다른 문제에서도 많이 쓰이는 것 같으니 알고 넘어가는 게 좋겠다 !

 

 

(+) 순환을 이용해서 풀 수 있지 않을까?? 시간될 때 순환으로 풀어봐야겠다.