늑대와 양

문제부터 파악해보자

1. 크기가 R*C인 목장이 있다.

2. 각각의 칸에는 비어있거나, 양 또는 늑대가 존재

2-1. 양은 이동하지 않고 지키고 있다. 늑대는 인접한 칸을 자유롭게 이동 가능

3. 목장에 울타리를 설치해서 양이 있는 칸으로 늑대가 못가게 막으려고 한다.

 

입력

1. 첫째줄: 목장 크기 R,C 주어짐

2. 둘째 줄: R개의 줄에 목장의 상태가 주어진다.

.은 빈칸, S는 양, W는 늑대

 

출력

첫째줄: 늑대가 양이 있는 칸으로 갈수 없게 할 수 있다면 1, 갈 수 있다면 0

둘째줄: R개의 줄에 목장의 상태를 출력한다. 

울타리는 'D'로 출력한다.

1. 당연히 우선너비탐색이 떠오름

- 전에 게시물이랑 매커니즘은 비슷하다.

2. 첫째줄에 갈 수 있냐 없냐

이분법이다. 둘 중 하나니깐 기본값을 Yes로 설정

3. 여러 경우를 돌려야 하니깐 for문을 이용하자

3-1. 늑대가 나올 경우?

양이 있으면 YES를 NO로 바꾸자

3-2. 양이 나올 경우?

그대로 YES

3-3. 비어있으면?

울타리 설치