[백준 C++] 16956 늑대와 양

문제

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

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

입력

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

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

출력

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

https://www.acmicpc.net/problem/16956

풀이

간단히 양이나 늑대주변 상하좌우에 울타리를 쌓으면된다.

스페셜 저지문제이므로, 하나의 입력에대해 여러개의 복수정답이 있을수있음.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::pair;
int r, c, ** farm;
vector<pair<int, int>> sheep, wolf;
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };

bool place_fence() {
	for (int i = 0; i < sheep.size(); i++) {
		int x = sheep[i].first;
		int y = sheep[i].second;

		for (int j = 0; j < 4; j++) { //양주변 4방향에 울타리설치
			int xx = x + dx[j];
			int yy = y + dy[j];

			if (0 <= xx && xx <= r - 1 && 0 <= yy && yy <= c - 1) {
				if (farm[xx][yy] == 2) { //늑대랑 붙어있을시 실패
					//printf(">> %d %d => %d %d\n", x, y, xx, yy);
					return false;
				}
				if (farm[xx][yy] == 0) farm[xx][yy] = 3; //비어있으면 울타리설치
			}
		}

	}
	return true;
}

int main(char temp) {
	scanf("%d%d", &r, &c);
	farm = new int* [r];
	for (int i = 0; i < r; i++) {
		farm[i] = new int[c];
		scanf("%c", &temp);
		for (int j = 0; j < c; j++) {
			scanf("%c", &temp);
			if (temp == 'S') { //양
				farm[i][j] = 1;
				sheep.push_back({ i, j });
			}
			else if (temp == 'W') { //늑대
				farm[i][j] = 2;
				wolf.push_back({ i, j });
			}
			else {
				farm[i][j] = 0;
			}
		}
	}

	if (place_fence()) {
		printf("1\n");
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++)
				if (farm[i][j] == 0)
					printf(".");
				else if (farm[i][j] == 1)
					printf("S");
				else if (farm[i][j] == 2)
					printf("W");
				else if (farm[i][j] == 3)
					printf("D");
			printf("\n");
		}
	}
	else {
		printf("0\n");
	}

	return 0;
}