[Inflearn #8] 봉우리

05 Jun 2022 in Study Log on Algorithm

• 문제 설명
• 문제 예제
• 풀이
• 설명

인프런 : JS 알고리즘 문제풀이

인프런 코테 대비 알고리즘 문제풀이를 정리해 놓은 것입니다.

문제 설명

봉우리

지도 정보가 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

풀이

// file: "solution.js"
function solution(arr) {
  let answer = 0;
  let n = arr.length;
  let dx = [-1, 0, 1, 0];  // #1
  let dy = [0, 1, 0, -1];  // #2
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {  // #3
      let flag = true;  // #4
      for (k = 0; k < dx.length; k++) {  // #5
        let nx = i + dx[k];  // 현재위치 i에서 좌우 탐색
        let ny = j + dy[k];  // 현재위치 j에서 상하 탐색
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {
          // 없는 값을 탐색하면 에러이기때문에 nx와 ny는 0보다 크거나 같고 n보다 작아야 한다.
          flag = false;  // #6
          break;
        }
      }
      if (flag) { // #7
        answer++;
      }
    }
  }
  return answer;
}

설명

1. 현재 위치(arr[i][j]) 에서 비교할 x 축 좌표를 설정합니다. 왼쪽(-1) 오른쪽(1)
2. 현재 위치(arr[i][j]) 에서 비교할 y 출 좌표를 설정합니다. 위(-1) 아래(1)
3. 행과 열에 접근하는 이중 반복문을 만든다.
4. 봉우리의 조건에 맞지 않으면 바로 넘기기 위한 boolean 변수를 생성해 준다.
5. 1,2번에서 설정한 것에 대한 반복문을 만든다. (현재 위치에서 상하좌우를 비교하기 위해)
6. 현재위치보다 상하좌우가 높으면 조건에 맞지 않기때문에 false를 담아주고 break를 한다.
7. flag가 true면 봉우리의 조건이 맞기 때문에 answer을 1씩 더해준다.