[BOJ16956] 늑대와 양

문제

• r*c 목장, 1*1 크기의 칸
• 비어있거나, 양(이동 x), 늑대(인접한 칸 이동 가능)
• 울타리 설치해 늑대가 양 못 잡아먹게하기

입력

• R, C(<= 500)
• 목장의 상태 (. S W)로 표현

출력

• 늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 1 출력, 있으면 0
• 둘째 줄부터 R 줄에는 목장 상태 출력, 울타리는 ‘D’

설계

• 늑대와 양이 바로 붙어있으면 무조건 잡아먹힘
• 아닌 상태라면, 늑대나 양의 사방에 울타리로 감싸기
• 양이 무슨 죄인가… 늑대 사방에 울타리 쳐서 풀었음

피드백

• 문제 연구소처럼 벽을 쳐서 막는 것인 줄 알고, 생각보다 까다로울 것이라 생각함
• 그런데 문제 노트에서 그냥 1, 0만 판단만 하면 되며, 울타리를 최소의 개수만 써야된다는 조건이 없었음
• DFS, BFS 같은 탐색 필요 없고, 늑대나 양 위치만 확인하여 사방 체크 후 울타리치기

How I solved(click to github)

---

ref :
BOJ16956