섹션 2. Array - 10. 봉우리

📌 문제 설명

N*N 격자판에 지역의 높이가 주어집니다. 격자판에서 자신의 상하좌우에 위치한 숫자보다 큰 숫자를 봉우리라고 합니다. 격자의 가장자리는 0으로 초기화되었다고 가정하고, 봉우리가 몇 개인지 알아내는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수 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으로 초기화된 것으로 간주하여 따로 경계를 체크하지 않아도 됩니다.

---

💻 코드 구현 (Java)

package partArray;

import java.util.*;

public class Problem10 {
	public int solution(int num, int[][] arr) {
		int answer = 0;
		
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, 1, 0, -1};
		
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num; j++) {
				boolean flag = true;
				for(int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if(nx >= 0 && ny >= 0 && nx < num && ny < num && arr[i][j] <= arr[nx][ny]) {
						flag = false;
						break;
					}
				}
				if(flag) answer++;
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Problem10 T = new Problem10();
		Scanner kb = new Scanner(System.in);
		int num = kb.nextInt();
		int[][] arr = new int[num][num];
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num; j++) {
				arr[i][j] = kb.nextInt();
			}
		}
		System.out.print(T.solution(num, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 상하좌우 탐색

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

• 좌표 이동을 위한 방향 배열입니다.

2️⃣ 봉우리 확인 로직

for(int k = 0; k < 4; k++) {
	int nx = i + dx[k];
	int ny = j + dy[k];
	if(nx >= 0 && ny >= 0 && nx < num && ny < num && arr[i][j] <= arr[nx][ny]) {
		flag = false;
		break;
	}
}

• 격자의 상하좌우 숫자와 비교하여 현재 위치보다 크거나 같은 숫자가 있으면 봉우리가 아닙니다.

---

⏳ 시간 복잡도 분석

• 각 셀을 최대 4번(상하좌우) 확인하므로 시간 복잡도는 O(N²)입니다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런