[배열] 10. 봉우리

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

 

 

 

<<풀이>>

-나의 풀이-

 

이 문제는 어렵지는 않다. 바깥이 0으로 둘러 쌓여 있다는 것을 감안해서 내부 값을 넣어준다고 생각했을 때, 원래 배열 크기에  2씩 증가시키면 된다. 그리고 값을 넣을 때도 이중 for문으로 1부터 n까지 대입해주면 된다.

 

그 다음 조건문에 &&를 많이 사용했지만 상하좌우 전부다 클 때, count 증가시켜서 최종 봉우리 수를 계산하면 된다.

 

import java.util.Scanner;

class Main {

    public int solution(int n, int[][] arr) {
        int count = 0;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (arr[i][j] > arr[i + 1][j] && arr[i][j] > arr[i][j + 1] && arr[i][j] > arr[i - 1][j] && arr[i][j] > arr[i][j - 1] ){
                    count++;
                }
            }
        }
        return count;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n + 2][n + 2];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        System.out.println(T.solution(n, arr));
    }
}

 

 

-강사님 풀이-

 

우선 이번 강사님의 풀이는 시간 복잡도는 나보다 복잡해 보인다.

하지만

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

 

이런 형식으로 두고 상하 좌우 값을 비교하는 하는데 이런 식은 지금은 몰라도 나중에 복잡해지면 유용하다.(그 문제를 제대로 만나 봐야 할거 같긴하다 ㅋㅋ)

 

아무튼 이러한 방식을 통해서 구할 수 있었고, boolean을 통해서 참이면 answer ++를 해줬다.

import java.util.Scanner;

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 T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n][n];
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < n ; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        System.out.println(T.solution(n, arr));
    }
}

 

 

<<추가 내용>>

1. 순서

특히 다시 상기시키고 기억해야 할 내용이 있다면, 바로 이 코드이다.

if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {
    flag = false;
    break;
}

 

if안에 있는 다항 연산의 순서도 중요하다. 처음 부터

arr[nx][ny] >= arr[i][j]

이러한 형식이 오면 틀리게 된다. 먼저 사용하지 못하는 nx, ny를 분류 해놓고 해야한다.

따라서 위의 첫번째 코드처럼 먼저 걸러 놓고 그다음 코드를 넣어야 한다.

 

2. break

break; 

-> 이는 실행하고 있는 반복분을 중지 시키고 그 외부의 코드가 돌아간다. 여기서 return을 넣게되면 아예 연산이 끝나고 종료 된다.