[알고리즘] 2차원 배열 시뮬레이션 - 봉우리

문제

---

지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다.
격자의 가장자리는 0으로 초기화 되었다고 가정합니다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

매개변수 board에 지도정보가 주어지면 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.

입출력 예

입력 예제

• [[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

풀이 방법

function solution(board) {
  const cnt = 0;
  let n = 5;

  return cnt;
}

• 봉우리 갯수를 count 할 수 있게 cnt값을 0으로 초기화 해줍니다.
• board.length를 변수 n으로 선언할 수도 있습니다.

function solution(board) {
  const cnt = 0;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  
  return cnt;
}

여기서 x는 행의 좌표, y는 열의 좌표를 의미하고, d는 방향을 나타냅니다.

• 특정 좌표 기준으로 (상, 우, 하, 좌)로 움직이는 x의 좌표를 dx변수에 초기화를 해줍니다.
• 특정 좌표 기준으로 (상, 우, 하, 좌)로 움직이는 y의 좌표를 dy변수에 초기화를 해줍니다.

function solution(board) {
  const cnt = 0;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      let flag = true;
    }
  }
  
  return cnt;
}

• 2차원 배열 탐색을 위해 2중 for문을 선언합니다
• 봉우리가 맞는지 알려주는 flag 변수를 true로 선언해줍니다.

function solution(board) {
  const cnt = 0;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      let flag = true;
      
      for (let k = 0; k < 4; k++) {
        let nx = i + dx[k];
        let ny = j + dy[k];
      }
   }
 }
  
 return cnt;
}

• x와 y좌표의 움직임을 위한 for문을 추가로 선언해줍니다.
• 이때 x와 y좌표는 (상, 우, 하, 좌) 총 4개의 방향으로만 이동하므로 k < 4 로 설정해줍니다.
• i는 x좌표 즉, 행의 움직임을 뜻하고, j는 y좌표 열의 움직임을 뜻합니다.
• i(행) 좌표에 x의 배열을 k 만큼 반복하는 값을 더해준 nx 를 선언합니다.
• j(열) 좌표에 y의 배열을 k 만큼 반복하는 값을 더해준 ny 를 선언합니다.

function solution(board) {
  const cnt = 0;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      let flag = true;
      
      for (let k = 0; k < 4; k++) {
        let nx = i + dx[k];
        let ny = j + dy[k];
        if (
          nx >= 0 && 
          ny >= 0 && 
          nx < n && 
          ny < n && 
          board[i][j] <= board[nx][ny]
        )
        {
          flag = false;
          break;
        }
      }
    }
  }
  return cnt;
}

• if 조건문안에 상하좌우로 움직이려는 행과 열의 움직임인 board[nx][ny]가 봉우리가 될 수 있는 값인 board[i][j] 보다 작거나 같다면 board[i][j]는 봉우리가 될 수 없습니다

• 행의 위치 index인 nx와 열의 위치 index인 ny는 0보다 커야합니다

• nx와 ny는 board의 길이인 n보다는 작아야합니다.

• 조건문에 해당되면 봉우리가 맞는지 알려주는 flag 변수를 false로 선언해줍니다.

• 그리고 반복문이 멈추도록 break를 넣어줍니다.

function solution(board) {
  const cnt = 0;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      let flag = true;
      
      for (let k = 0; k < 4; k++) {
        let nx = i + dx[k];
        let ny = j + dy[k];
        if (
          nx >= 0 && 
          ny >= 0 && 
          nx < n && 
          ny < n && 
          board[i][j] <= board[nx][ny]
        )
        {
          flag = false;
          break;
        }
      }
      if (flag) cnt++;
    }
  }
  return cnt;
}

• 위의 조건문에서 해당 되지 않고 flag가 true 라면, 봉우리 갯수를 카운트하는 cnt를 1씩 더해줍니다.