[알고리즘] flag변수를 이용한 봉우리 개수 구하기

❓봉우리 개수 구하기

 

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

만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

▣ 입력설명
첫 줄에 자연수 N이 주어진다.(1<=N<=50)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는 다.

▣ 출력설명
봉우리의 개수를 출력하세요.

▣ 입력예제 1 5
53723 37161 72534 43641 87352

▣ 출력예제 1 10

 

function solution(arr) {
    let answer = 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 // boolean 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]) {
                    flag = 0;   // boolean false를 뜻함
                    break;
                }
            }
            if (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));

 

💡 문제 풀이

 

1. for문이 몇 번 돌 것인지 n 변수에 길이를 담아준다.

2. 자신을 기준으로 상우하좌 시계 방향으로 돌아가며 비교할 것이기 때문에 행(dx), 열(dy) 변수에 어떻게 변화하며 비교할 것인지 정해준다. (상하좌우, 좌상우하, 상우하좌 순서는 상관 없습니다.) 자신을 기준으로 위쪽과 비교하려면 가지고있는 좌표에서 (행,열)이므로 (-1, 0)이 되어야하고 오른쪽과 비교하려면 (0, 1)이 더해져 이동해야합니다. 각각 맞춰서 dx와 dy에 배열로 담아주면 됩니다.

3. 2중 for문을 돌것인데 횟수는 받은 배열의 길이값 보다 적어야합니다.

4. flag 변수를 사용해 줄 것인데, flag 변수란 상태를 기록하고 처리 흐름을 제어하기 위한 boolean 변수 입니다. boolean에서 1은 true를 의미하고 0은 false를 의미합니다.

5. 그리고 비교해주기 위한 for문을 작성합니다. for문의 길이는 상하좌우 4번만 해주면 된다고 정해져 있으니 그대로 적용해주고, 새로운 변수를 정할건데 이것은 가려고 하는 방향(비교할 대상)의 좌표를 구하기 위함입니다.
nx는 행에서 비교할 대상의 좌표 (i + dx[k]) ny는 열에서 비교할 대상의 좌표 (j+dy[k])로 설정해줍니다.

6. if문을 사용하여 참 거짓을 구분하여 flag 변수에 어떤 값을 넣어줄지 설정합니다. if문 조건절에 받은 배열의 좌표가 0~(n-1) 까지인데 -(마이너스)의 값이 나와서는 안되니 비교연산자와 논리연산자를 이용하여 0보다 크고 n보다 작게 만들고,
받은 배열(arr)에서 arr[nx][ny](비교대상) >= arr[i][j](기준) 에 해당되면 flag를 0(false)으로 바꿔주고 break를 사용하여 if문을 종료시킵니다.

7. flag변수가 1(true)라면 answer에 값을 더해주고, 0(false)라면 더해주지 않고 값을 도출합니다.