[JS] 알고리즘 기초 정복 2-7번 - 봉우리 🌟

문제 2-7번

지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

 

🍄 입력설명

첫 줄에 자연수 N이 주어진다.(1<=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이므로 양 끝 줄의 수는 4방면을 모두 탐색할 필요가 없다. 4방면 중 하나라도 자신보다 높다면 반복문을 멈추고(break), 모두 낮다면 그때 answer(봉우리갯수)을 1씩 증가시킨다. 

function solution(arr) {
	let answer = 0;
	let n = arr.length;
	let dx = [-1, 0, 1, 0]; // 12시 방향, 3시 방향, 6시 방향, 9시 방향(행)
	let dy = [0, 1, 0, -1]; //열

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			let flag = 1; //봉우리
				for (let k = 0; k < 4; k++) {
					let nx = i + dx[k]; // 방향 탐색하는 행 좌표
					let ny = j + dy[k]; // 방향 탐색하는 열 좌표
					if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {
						flag = 0;
						break; // 하나라도 커버리면 봉우리가 아니니 더 탐색할 필요 없어서 break 종료
					}
				}
				if (flag) answer++; 
                //flag가 1이라면 = true 라면 answer(봉우리갯수) 값을 1씩 증가
		}
	}

	return answer;
}

let arr = [
[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],
];
console.log(solution(arr));
// 10 출력