JS알고리즘 | 봉우리 (2차원 배열 네방향 탐색)

탐색문제 유형 중 하나인 봉우리 개수를 찾는 문제이다.

 

문제

N*N격자판이 주어지고 높이가 쓰여있다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이다. 봉우리 지역이 몇 개인지 알아내는 프로그램을 작성해보자. 

 

입력예제 |

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

출력예제 |

10

 

접근

1. 기준점을 정하고 네 방향을 탐색한다. 이중 for문으로 2차원 배열을 탐색한다. (if문 남발하지않고 작성)

2. 배열의 각 요소를 탐색하면서 상하좌우 크기 비교 -> 나보다 큰게 없으면 봉우리다 -> 카운팅한다.

 

 

풀이

세부적으로 풀이를 해보면,

 

1.

내 좌표(기준점) 에서 상하좌우 좌표를 구해야한다. 

자신과 상하좌우 숫자를 비교해야한다. 움직여야할 행과 열을 배열로 작성한다. (시계방향) 

행과 열은 세트로 움직인다. 

 

상, 하 → 행 이동

행 = [상, 우, 하, 좌] →  dx = [-1, 0, 1, 0] 

좌, 우 → 열 이동

열 = [상, 우, 하, 좌] →  dy = [0, 1, 0, -1] 

 

2.

내 좌표(기준점)은 i과 j가 이중for문을 돌면서 좌표를 구한다. 

 

3.

상하좌우, 4번 k for문 돌아야한다.

내 좌표의 값과 네 방향의 좌표 비교해서, 네 방향이 더 작으면 answer++한다. 

let nx = i+dx[k]; → i에 -1이나 1을 더해 행을 옮긴다 (상하이동)
let ny = j+dy[k]; → j에 -1이나 1을 더해 열을 옮긴다 (좌우이동)

상 → 행이 -1로 이동할 때 열은 0 이동 (열 이동없음)

하 → 행이 1로 이동할 때 열은 0 이동 (열 이동없음)

좌 → 열이 1 이동할 때 행은 0 이동 (행 이동없음)

우 → 열이 -1 이동할 때 열은 0 이동 (행 이동없음)

 

4.

flag는 봉우리인지 아닌지 체크한다.

flag가 0이면 answer 카운팅 안되고, 1이면 카운팅된다. 

 

코드

function solution(arr){
            let answer = 0; //카운팅해야되니까 0으로 
            let n = arr.length;
            let dx = [-1, 0, 1, 0];
            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++){ // 4방향이라서 4번돌도록 맞춤
                        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]){ 
                            // arr[nx][ny]상하좌우좌표 >= 현재지점좌표 arr[i][j]
                            // nx>=0 && nx<n && ny>=0 && ny<n는 
                            // 내 상하좌우가 네방향으로 존재하지 않는 경우도 있으니 그 경우는 제외하는 조건
                            // 현재지점 좌표보다 큰게 있으면 봉우리가 아니다. 이걸 확인하기 위해서 flag변수 작성해준 것
                            flag=0;
                            break; // k for문 멈춤
                        }  
                    }
                    if(flag) answer++; 
                    // 상하좌우 다 돌고 나와서 flag가 그대로이면 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));