양치기 꿍

양치기 꿍

문제 설명

양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다.

하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다.

꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산할 수 있겠는가?

단, 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다.

예제 입력

6 6
...#..
.##v#.
#v.#.#
#.k#.#
.###.#
...###

📤 예제 출력

0 2

---

문제 풀이

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 arr = [];
  const [R, C] = input[idx++].split(" ").map(Number);
  for (let i = 0; i < R; i++) {
    arr.push(input[idx++].split(""));
  }
  let v = 0;
  let k = 0;
  // 델타 배열
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  // 방문 체크용 2차원 배열
  const visited = Array.from({ length: R }, () => Array(C).fill(false));
  // dfs 함수
  const dfs = (x, y) => {
    // 만약 현재 원소가 v 라면 v 값 증가(늑대)
    if (arr[x][y] === "v") v++;
    // k 라면 k 값 증가(양)
    else if (arr[x][y] === "k") k++;
    // 방문 체크
    visited[x][y] = true;
    // 델타 탐색
    for (let k = 0; k < 4; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      // 범위에 벗어나지 않고 방문하지 않았으며 울타리가 아니라면
      if (
        0 <= nx &&
        nx < R &&
        0 <= ny &&
        ny < C &&
        !visited[nx][ny] &&
        arr[nx][ny] != "#"
      ) {
        // dfs 수행
        dfs(nx, ny);
      }
    }
  };
  // 결과값 저장 배열
  let total = [0, 0];
  // 2차원 배열 반복
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      // 방문하지 않았고 울타리가 아니라면
      if (!visited[i][j] && arr[i][j] !== "#") {
        // dfs 수행
        dfs(i, j);
        // dfs 수행 종료후 나왔을 때 양이 더 많다면 양에 합산
        if (k > v) total[0] += k;
        // 그 외의 경우라면 늑대에 합산
        else total[1] += v;
        // 새롭게 탐색할 수 있도록 늑대와 양 값 초기화
        v = 0;
        k = 0;
      }
    }
  }
  console.log(total.join(" "));
};
solution(input);

아이디어 / 접근법

1. 델타 탐색 + dfs
2. dfs 내부에서 양의 개수와 늑대의 개수 탐색
3. 반복문 + dfs 를 통해 울타리 내부의 늑대와 양의 개수를 판별하고 결과 값에 어떤 쪽이 더 많이 살아남았는 지 누적

후기

델타와 dfs를 다룰 줄 안다면 기본적으로 쉬운 문제였음.