-
백준(BOJ) 16956번 늑대와 양알고리즘 풀이/백준(Boj) 2019. 12. 29. 02:39
문제 : https://www.acmicpc.net/problem/16956
16956번: 늑대와 양
크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다. 목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.
www.acmicpc.net
풀이 :
1. S의 상하좌우의 W가 있다면 울타리를 만들 수 없으니 0을 출력할 수밖에 없다.
2. S의 상하좌우의 W인 곳이 없다면 모두 울타리를 만들 수 있으니 1을 출력하고 임의대로 울타리를
만들어주자. 많은 답이 있겠지만 나의 경우는 상하좌우에 울타리를 둘러주었다.
코드( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 매직 스퀘어로 변경하기 (0) 2020.01.01 백준(BOJ) 17779번 게리맨더링2 (0) 2020.01.01 백준(BOJ) 16959번 체스판 여행 1 (0) 2019.12.26 백준(BOJ) 17822번 원판 돌리기 (0) 2019.12.23 백준(BOJ) 17143번 낚시왕 (0) 2019.12.19