[백준 16956] 늑대와 양

풀이

약간의 트릭만 잘 찾아내면 쉽게 문제를 해결할 수 있다.

 

울타리의 최소 개수를 구하는 문제가 아니라, 울타리를 설치해서 양을 늑대로부터 보호에 성공한다면 양은 사는 것이고 아니라면 양은 늑대에게 잡아먹히게 된다.

 

양이 늑대로부터 살려고 한다면?

가장 간단한 방법은 양의 상, 하, 좌, 우 방향으로 울타리를 설치하면 된다.

그러고 나서 늑대가 맵을 탐색 하면서 양을 찾아내지 못한다면 양은 사는 것이고, 아니라면 잡아먹힌다.

 

1. 양의 상,하,좌,우 방향으로 울타리를 설치한다. (이때 빈칸인 경우에만 울타리를 설치하자.)

2. 늑대가 양을 찾는다.

 

#include <iostream>
#include <queue>
using namespace std;

int r, c;
char board[501][501];
bool vis[501][501];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

void print()
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cout << board[i][j];
		}
		cout << '\n';
	}
	cout << '\n';
}

bool findSheep(int x, int y)
{
	queue<pair<int, int >> q;
	q.push({ x,y });
	vis[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < r && ny < c)
			{
				if (board[nx][ny] == 'S' && !vis[nx][ny]) 
					return true;
				else if (board[nx][ny] != 'D' && !vis[nx][ny])
				{
					vis[nx][ny] = true;
					q.push({ nx,ny });
				}
			}
		}
	}

	return false;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> r >> c;
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> board[i][j];

	bool find = false;
	// 양의 4방향으로 울타리를 설치하자.
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (board[i][j] == 'S')
			{
				for (int k = 0; k < 4; ++k)
				{
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (nx >= 0 && ny >= 0 && nx < r && ny < c)
					{
						if (board[nx][ny] == '.')
							board[nx][ny] = 'D';
					}
				}
			}
		}
	}

	// 늑대가 양을 찾는다.
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (board[i][j] == 'W' && !vis[i][j])
			{
				find = findSheep(i, j);
			}
		}
	}

	if (find)
		cout << 0 << '\n';
	else
	{
		cout << 1 << '\n';
		print();
	}

	return 0;
}