봉우리

설명

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

 

 

문제 분석 및 코드 분석

 💡 상하좌우 완전 탐색

 

 

현재 위치를 찾고 이를 기준으로 상하좌우 탐색합니다.

 

1. 현재 위치

   2차원 배열을 탐색합니다. - 현재 위치  i, j가 결정됨

for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
        ...
        }
}

 

2. 현재 위치  i,j가 결정되고 k가 이동하면서 상하좌우 탐색

→ 탐색한 위치가 현 위치보다 크면 현 위치는 봉우리가 아닙니다. 

for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<4; k++){
                int nx=i+dx[k];
                int ny=j+dy[k];
            }
        }
}

 

3. 🔊 경계선 처리

경계선이 전부 0이므로 2번에서 '탐색한 위치가 현 위치보다 크면 현 위치는 봉우리가 아니다. '하기 전에

경계선 처리를 해주어야 합니다. 해주지 않고 실행했을 때 ArrayIndexOutBoundsException에러가 발생합니다.

 

 

문제 분석한 것을 토대로 코드 작성을 해보겠습니다.

 

 

 

실패 코드

import java.util.Scanner;

public class Main {
	static int answer = 0;
	int[] dx = {-1,0,1,0};
	int[] dy = {0,1,0,-1};
	
	public void Peaks(int n, int[][] arr) {
		// 현재 나의 위치
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				// k로 상하좌우 이동
                		// 현 위치가 봉우리가 아니라면 signal false 처리하여 answer에 카운트 되지 못하게 함
				boolean signal = 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]) {
						signal = false;
						return; // [[ !! 범인 !! ]] 	
					}
				}
				if(signal) answer ++;
			}
		}	
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		// 입력 : n, n*n에 담을 배열
		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();
			}
		}
		T.Peaks(n, arr);
		System.out.println(answer);
	}
}

 

 

원인

if문을 종료시키는데 break문을 사용하지 않고 return을 사용했습니다.

💡 break는 해당 if문만 종료시키지만,
    return은 해당 메서드가 호출된 곳까지 종료시킵니다, 즉, if문을 포함한 메소드 자체를 종료시키므로
    주의해서 사용해야 합니다.

 

 

 

성공 코드

import java.util.Scanner;

public class Main {
	static int answer = 0;
	int[] dx = {-1,0,1,0};
	int[] dy = {0,1,0,-1};
	
	public void Peaks(int n, int[][] arr) {
		// 현재 나의 위치
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				// k로 상하좌우 이동
                		// 현 위치가 봉우리가 아니라면 signal false 처리하여 answer에 카운트 되지 못하게 함
				boolean signal = 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]) {
						signal = false;
						break;
					}
				}
				if(signal) answer ++;
			}
		}	
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		// 입력 : n, n*n에 담을 배열
		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();
			}
		}
		T.Peaks(n, arr);
		System.out.println(answer);
	}
}