[백준] 16956번: 늑대와 양 (Node.js)

백준에서 16956번: 늑대와 양 (난이도: Silver III) 확인하기 

 

1. 문제

 

크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.

 

목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.

 

 

1-1. 입력

첫째 줄에 목장의 크기 R, C가 주어진다.

둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.

 

1-2. 출력

늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

 

---

 

2. 풀이 

 

const [info, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [Y, X] = info.split(' ').map(val => +val);
const farm = input.map(row => [...row]);

const dirs = [
  [0, 1],
  [0, -1],
  [-1, 0],
  [1, 0],
];

const isSheepSafe = (x, y) => {
  let safety = true;

  dirs.forEach(dir => {
    const xPos = dir[0] + x;
    const yPos = dir[1] + y;

    if (xPos >= 0 && yPos >= 0 && xPos < X && yPos < Y) {
      if (farm[yPos][xPos] === 'W') safety = false;
    }
  });

  return safety;
};

const blockWolves = () => {
  for (let y = 0; y < farm.length; y++) {
    const row = farm[y];

    for (let x = 0; x < row.length; x++) {
      if (row[x] === 'S') {
        const safety = isSheepSafe(x, y);

        if (!safety) return 0;
      }
    }
  }

  const maxSafetyFarm = farm.map(row => {
    return row.join('').replaceAll('.', 'D');
  });

  return '1' + '\n' + maxSafetyFarm.join('\n');
};

console.log(blockWolves());

 

2-1. 접근 방식 

 

늑대로부터 양을 보호하는 데 필요한 최소한의 울타리 수를 구하는 문제가 아니라, 양과 늑대를 완전 분리시킬 수 있는지 확인하는 문제다. 즉, 농장의 형태가 어떻게 되어있든 늑대(W)와 양(S)이 완전 분리만 되어 있으면 된다. 

 

반복문으로 순회하면서 양(S)을 만날 때 마다 'isSheepSafe()'라는 헬퍼 함수를 호출하여 양의 좌우상하 칸에 늑대가 있는지 확인했다. 늑대와 양이 인접 칸에 위치한 경우 어떻게 울타리를 쳐도 양이 안전할 수 없기 때문에 바로 0을 반환했다. 

 

반대로 늑대와 양이 붙어있지 않은 경우 농장에 있는 모든 빈 공간(마침표)를 울타리(D)로 바꾼 뒤, 1과 함께 출력해줬다.