농장 관리

농장 관리

문제 설명

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. 여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이가 모두 1 이하인 경우이다. 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

예제 입력

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

예제 출력

3

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let idx = 0;
  const [N, M] = input[idx++].split(" ").map(Number);
  const arr = [];
  for (let i = 0; i < N; i++) {
    arr.push(input[idx++].split(" ").map(Number));
  }
  // 좌표 탐색 조건은 하나의 좌표 차이기 때문에 대각선도 모두 고려해야 함
  const dx = [-1, 1, 0, 0, -1, 1, 1, -1];
  const dy = [0, 0, -1, 1, -1, 1, -1, 1];
  // 방문 체크 배열
  const visited = Array.from({ length: N }, () => Array(M).fill(false));
  // 현재 산봉우리 높이와 다음 산봉우리 높이를 체크하기 위한 변수
  let check = false;
  // dfs 시작
  const dfs = (x, y) => {
    // 방문 체크
    visited[x][y] = true;
    // 8방 탐색
    for (let k = 0; k < 8; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      // 경계 조간
      if (0 <= nx && nx < N && 0 <= ny && ny < M) {
        // 만약 다음 산봉우리가 현재 산봉우리보다 높다면 유효하지 않은 산봉우리
        if (arr[x][y] < arr[nx][ny]) check = false;
        // 방문하지 않았고 다음 높이가 현재 위치와 같다면 재귀 호출
        if (!visited[nx][ny] && arr[x][y] === arr[nx][ny]) {
          dfs(nx, ny);
        }
      }
    }
  };
  let cnt = 0;

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (!visited[i][j]) {
        // 초기 check 값 설정
        check = true;
        dfs(i, j);
        // check 값이 true 라면(산봉우리 탐색 완료) cnt 추가
        check ? cnt++ : "";
      }
    }
  }
  console.log(cnt);
};

solution(input);

아이디어 / 접근법

1. DFS 혹은 BFS 로 산봉우리 탐색
2. 만약 다음 좌표의 높이가 현재 위치보다 크다면 탐색하지 않음
3. 만약 다음 좌표가 현재 좌표와 같다면 탐색 진행(어차피 작은 좌표는 볼 필요 없고 나랑 같은 높이만 판별하면 됨)
4. 탐색 후 결과 갱신

후기

문제 자체는 델타 + DFS || BFS 문제인데 이제 탐색 조건을 하나 더 걸어줘야 했음 내 높이보다 다음 높이가 크면 탐색을 진행하면 안되고 높이가 낮은 경우 어차피 볼 필요가 없음 그래서 사실상 현재 좌표에서 가장 높은 높이를 찾고 그 높이가 인접한 곳에 또 존재하면 그게 가장 높은 산봉우리가 되는 것임 그래서 결론적으로 가장 높은 높이를 찾고 혹시 주변에 동일한 높이를 가진 산봉우리가 있는 지를 판별하는 문제였음.