[배열탐색] 봉우리

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

지도의 정보가 N*N 격자판에 주어지고 각 격자에는 그 지역의 높이가 쓰여있다.

각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이다.

지도의 정보가 주어지면 봉우리 지역의 개수를 출력한다.

 

만약 N = 5이고 지도의 정보가 다음과 같다면 봉우리는 표시된 것과 같고 개수는 10개이다.

5	4	7	2	3
3	7	1	6	1
7	2	5	3	4
4	3	6	4	1
8	7	3	5	2

 

 

👉 입력

N줄의 걸쳐 N개의 자연수가 주어진다.

각 자연수는 100을 넘지 않는다.

 

 

👈 출력

봉우리의 개수를 출력한다.

 

 

📝 풀이

 

function solution(arr) {
    let answer = 0;
    let n = arr.length;
    let dx = [-1, 1, 0, 0]; // 상하좌우
    let dy = [0, 0, -1, 1];

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            let isMax = true;
            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]
                ) {
                    isMax = false;
                    break;
                }
            }
            if (isMax) answer++;
        }
    }
    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));

 

먼저 자신과 자신으로부터 상, 하, 좌, 우에 있는 요소를 비교해야 한다.

만약 현재 자신이 (1, 2)라고 하면

• 상 : (0, 2)
• 하 : (2, 2)
• 좌 : (1, 1)
• 우 : (1, 3)

이렇게 네 개의 좌표의 요소와 비교해야 한다.

 

다시 자신의 좌표를 (i, j)라고 표현해본다면

• 상 : (i - 1, j)
• 하 : (i + 1, j)
• 좌 : (i, j - 1)
• 우 : (i, j + 1)

이렇게 네 개의 좌표의 요소와 비교해야 한다.

 

따라서 행의 정보를 dx에, 열의 정보를 dy에 담아 상하좌우로 이동할 정보를 다음과 같이 표현할 수 있다.

let dx = [-1, 1, 0, 0]; // 상하좌우
let dy = [0, 0, -1, 1];

 

이후 격자판의 각 요소를 순회하기 위해 이중 for문을 돈다.

또한 dx, dy를 이용해 해당 요소의 상하좌우를 탐색하기 위한 for문을 하나 더 돈다.

이 for문을 돌기 전 현재의 요소를 최댓값이라 가정하고 이를 뜻하는 변수 isMax에 true를 넣어준다.

 

제일 안쪽의 for문 안에서 nx와 ny에 상하좌우의 좌표를 담아 현재의 arr[i][j]보다 큰 값이 있는지 비교한 후 자신보다 큰 값이 있다면 isMax를 false로 바꿔주고 for문을 빠져나온다.

(큰 값이 하나라도 있다면 봉우리가 아니기 때문에 다른 값은 안 살펴봐도 된다.)

nx >= 0 && nx < n && ny >= 0 && ny < n 의 조건을 추가로 주는 이유는 경계선에 있는 값들은 배열의 범위 내에 있는 값만 비교하도록 하기 위해서 이다.

 

상하좌우의 값과 비교하는 작업이 끝났다면 isMax변수의 값을 확인하고 true라면 봉우리의 개수를 저장할 변수인 answer에 1을 더해준다.

이후 모든 작업이 끝나면 answer의 값을 출력한다.