[Beakjoon] 16956번 늑대와 양

📣
Beakjoon에서 PASS된 코드만 업데이트합니다.
알고리즘을 먼저 풀이하는 언어(Java)가 정해져있어, 풀이 언어(Python, C++, Java)가 모두 업데이트될 때까지는 시간이 걸릴 수 있습니다.

문제 제시

---

문제

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

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

입력

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

출력

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

제한

• 1 ≤ R, C ≤ 500

문제 풀이

---

문제의 입출력 예시를 보고 풀려고 하면 매우 어려워집니다.
저 역시 이 문제의 입력값에 대해서 출력값이 어떻게 나오게 되는 건지 꽤 오래 고민했습니다.

이 문제 분류는 스페셜 저지입니다!
출력 값이 예시처럼이 아닌 다양한 경우로 나와도 됩니다.

즉, 유무를 판단하는 0과 1의 출력값을 제외한, 목장에 대한 정보는 전혀 다르게 나와도 괜찮은 것이죠.


이렇게 되면 접근이 조금 더 쉬워집니다.
현재 문제의 울타리의 수는 제한이 없으며, 몇개를 넣어도 무관한 것이죠.

따라서 늑대의 정보를 저장하고 4방을 확인하면서 검사하는 방식을 적용할 것입니다.
이렇게 검사를 하는 중에 발생할 수 있는 상황은 총 4가지 입니다.

• 양(‘S’)이 있는 경우 : 바로 0을 출력하면 됩니다.
• 늑대(‘W’)가 있는 경우 : 늑대도 무조건 1마리라는 보장이 없으며, 늑대 옆에 늑대가 있을 수 있습니다.
  늑대와 늑대는 서로의 간섭대상이 아니므로 무시합니다.
• 울타리(‘D’)가 있는 경우 : 이미 제한되어있으므로, 늑대는 더 확인할 수 없어 다음 방향을 확인합니다.
• 빈칸(‘.’)인 경우 : 무조건 울타리를 설치하는 대상이 됩니다.

빈칸이 인접하면 무조건 울타리를 설치하는 것은 늑대를 1x1m의 공간에 가두는 것입니다.
인정머리 없지만… 양을 지켜야죠! 🐏 ㅎㅎ

이렇게 모든 늑대의 주위를 확인하며 울타리를 선택하는데 양을 만나지 않고 끝난다면,
늑대를 안전하게 모두 가둔 것입니다.
이 상태의 목장 정보를 함께 출력하면 되겠습니다.

• 늑대 정보 : Class 형식으로 저장
• 늑대들의 정보 : Queue형식으로 저장
• 모든 정보 확인 : Delta 활용

문제 코드

Java

제출 결과