알고리즘) 봉우리 수 구하기

 봉우리란, N*N 형태의 격자판에서 주변(상하좌우)의 값보다 높은 값을 가지는 인덱스들이 봉우리가 된다. 주변과 같은 값이 있다면 봉우리가 아님에 유의하자. + 격자판은 0으로만 구성된 행, 열에 감싸진다. (격자판의 상하좌우 마지막 행, 열은 모두 0으로 구성되어있다.)

초기 작성 코드

import java.util.Scanner;

public class Main {
    private int solution(int n, int[][] grid) {
        int answer = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i][j] > grid[i][j - 1] && grid[i][j] > grid[i][j + 1]) {
                    if (grid[i][j] > grid[i - 1][j] && grid[i][j] > grid[i + 1][j]) {
                        answer++;
                    }
                }
            }
        }
        return answer;
    }

    public static void main(String args[]) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();

        int[][] grid = new int[num + 2][num + 2];
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= num; j++) {
                grid[i][j] = sc.nextInt();
            }
            sc.nextLine();
        }
        System.out.println(al.solution(num, grid));
    }
}

 

개선 코드

import java.util.Scanner;

public class Main {
    private int solution(int n, int[][] grid) {
        int answer = 0;

        int[] ny = {0, 1, 0, -1};
        int[] nx = {-1, 0, 1, 0};
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                boolean flag = true;
                for (int k = 0; k < 4; k++) {
                    if (grid[i][j] <= grid[i + ny[k]][j + nx[k]]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) answer++;
            }
        }

        return answer;
    }

    public static void main(String args[]) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();

        int[][] grid = new int[num + 2][num + 2];
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= num; j++) {
                grid[i][j] = sc.nextInt();
            }
            sc.nextLine();
        }
        System.out.println(al.solution(num, grid));
    }
}

 

 개선된 방식은 인덱스의 상하좌우 검사를 위해 자신의 인덱스를 기준으로 더해질 값들을 배열로 만들었다고 볼 수 있다. ny와 nx는 모두 같은 인덱스값으로 조회된다. (ny, nx) 쌍을 지어보자면, (0, -1)은 같은 행의 좌측으로 한 칸 앞의 인덱스로 격자판에서 해당 인덱스의 왼쪽 값을 가리킨다. 다음으로 (1, 0)은 다음 행(바로 아래 줄)의 값으로, 격자판에서 해당 인덱스의 아래 값을 가리킨다. 이런 식으로 위의 코드는 검사하려하는 인덱스를 기준으로 반시계방향의 네 개 값을 확인하는 것이다. 하나라도 자신보다 크거나 같은 값이 있다면 flag 값을 변화시켜 검사 loop를 다 돌린 후 해당 flag값이 변경되지 않은 경우에만 봉우리 수를 증가시키는 것이다.