봉우리

문제

 지도 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자

 는 봉우리 지역이다. 봉우리 지역이 몇 개 있는지 알아내고자 한다.

 (격자의 가장자리는 0으로 초기화 되었다고 가정한다.)

 

문제풀이

격자의 가장자리는 0으로 초기화되어 있기 때문에 높이를 비교할 필요가 없이 이보다 항상 크다.

 

격자의 가장자리인 0에 인접한 영역(보라색)과 그렇지 않은 영역(주황색)을 두 개로 나눠 반복문을 수행한다.

격자의 가장자리인 0에 인접한 영역은 인덱스 값에 따라 각 방향에서 제외되는 영역이 존재하기 때문이다.

(비교하고자 하는 값은 언제나 0보다는 크기 때문이다)

 

이때 격자의 가장자리 0에 인접한 영역 중 4군데의 모서리 영역(5, 3, 8, 2)는 각각 다른 방향으로 두 군데의 격자의 가장자리와 인접해 있기 때문에 해당하는 방향의 인덱스는 계산에서 제외해 준다.

 

비교하고자 하는 중심 요소 값인 center[i][j]에서 각 방향값은 다음과 같다.

위: (i - 1, j) 

아래: (i +1, j)

오른쪽: (i, j + 1)

왼쪽: (i, j - 1)

 

코드

function solution(num, height) {
  let answer = [];
  let top, bottom, left, right;

  for (let i = 0; i < num; i++) {
    let max = 0;
    for (let j = 0; j < num; j++) {
      let center = height[i][j];
      if (i === 0) {
        bottom = height[i + 1][j];
        right = height[i][j + 1];
        left = height[i][j - 1];
        if (j === 0) {
          let max = Math.max(center, bottom, right);
          if (center === max) {
            answer.push(max);
          }
        } else if (j === 4) {
          let max = Math.max(center, bottom, left);
          if (center === max) {
            answer.push(max);
          }
        }
        let max = Math.max(center, bottom, right, left);
        if (center === max) {
          answer.push(max);
        }
      }
      if (i === 4) {
        top = height[i - 1][j];
        right = height[i][j + 1];
        left = height[i][j - 1];
        if (j === 0) {
          let max = Math.max(center, top, right);
          if (center === max) {
            answer.push(max);
          }
        } else if (j === 4) {
          let max = Math.max(center, top, left);
          if (center === max) {
            answer.push(max);
          }
        }
        let max = Math.max(center, top, right, left);
        if (center === max) {
          answer.push(max);
        }
      }
      if (0 < i && num - 1 > i) {
        if (j === 0) {
          top = height[i - 1][j];
          right = height[i][j + 1];
          bottom = height[i + 1][j];

          let max = Math.max(center, top, right);
          if (center === max) {
            answer.push(max);
          }
        } else if(j === 4) {
          top = height[i - 1][j];
          left = height[i][j - 1];
          bottom = height[i + 1][j];

          let max = Math.max(center, top, left);
          if (center === max) {
            answer.push(max);
          }
        }
      }
    }
  }
  top, bottom, left, (right = 0);
  for (let i = 1; i < num - 1; i++) {
    let max = 0;
    for (let j = 1; j < num - 1; j++) {
      let center = height[i][j];
      top = height[i - 1][j];
      bottom = height[i + 1][j];
      left = height[i][j - 1];
      right = height[i][j + 1];

      let max = Math.max(center, top, bottom, left, right);
      if (center === max) {
        answer.push(max);
      }
    }
  }

  return answer.length;
}

let height = [
  [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(5, height));

 

개선사항

각 방향값에 대한 인덱스의 값은 항상 고정적이기 때문에 모든 수행문에서 공통적으로 쓰일 수 있도록 하는 것이 좋다.

 

격자의 가장자리인 0에 인접한 영역과 그렇지 않은 영역을 두개로 나눠 반복문을 수행한 결과 동일한 연산들이 진행되어 코드 상 효율적이지 못했다. 영역을 구분하기 보단 3중 for을 수행한다. 마지막 for문 내에서 행과 열에 대한 방향값들을 반복적으로 변수에 할당하여 이를 통해 참조하고자 하는 인덱스의 높이가 봉우리에 해당하는지 확인한다.

 

격자의 가장자리 영역들이 봉우리인지 확인할 때, 각 인덱스 값에 따라 제외되는 방향이 있다. 이때 제외되는 방향값은 index out of range 에러를 발생시킨다.(0은 실제 배열 내에 요소로 존재하는 것이 아니라 가정 하에 둔 것이기 때문이다) 본 에러를 조건문에 이용하여 해당 방향값이 본 배열의 인덱스 범위 내에서 벗어날 경우엔 비교 연산을 하지 않고 그대로 다음 반복문을 수행하도록 한다.

 

봉우리가 되기 위한 조건 상 인접한 영역 중 하나라도 자신보다 큰 값을 지닌 요소가 있을 경우에는 만족하지 않기 때문에 대소 비교 시 인접한 영역들 중에 하나라도 큰 값이 있다면 해당 값을 정답에서 제외한다.

 

코드

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;
                        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;
                            }
                        }
                        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));