백준 26076 곰곰이의 식단 관리 2

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

26076번: 곰곰이의 식단 관리 2

 

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제

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

2667번: 단지번호붙이기

BFS를 사용해서 풀겁니다. BFS의 그룹마다 번호도 붙여야되므로 해당 문제가 필수입니다.

 

 

1. 핵심 아이디어

 

모서리에 있는 곰곰이나 치킨만 가두면되므로 장애물은 많아야 2개만 깔면된다.

즉 답으로 나올 수 있는 경우의 최대 갯수는 2개라는 뜻이다.

 

파랑색이나 빨간색으로 표시한곳에 장애물을 세우면 끝난다.

 

그렇다면 장애물을 0개 or 1개 세우는 경우는 어떠한 경우가 있을까?

 

0개 세우는 경우를 파악하는 방법은 간단하다.

곰곰이와 치킨의 공간이 두 공간으로 나뉘었는지 파악하면된다.

BFS를 통해서 곰곰이에서 치킨까지 도달 할 수 있는지 확인해본다.

장애물로 인해서 곰곰이와 치킨이 나뉘어져있다. 곰곰이는 치킨에게 도달할 수 없다.

 

1개를 세우는 방법은 다음과 같다.

 

격자판의 밖에 다음과 같은 빨강색과 파란색으로 장애물이 더 있다고 생각하고

빨강장애물과 연결된 장애물과 파란장애물과 연결된 장애물을 표시해보면 다음과 같이 나온다.

 

 

장애물을 배치할 공간중에서 ←→↑↓↖↗↙↘의 칸을 확인해서 파랑장애물과 빨간장애물을 모두 포함하고 있다면

해당 공간에 장애물을 배치하면 치킨과 곰곰이를 분리할 수 있다는 것을 알 수 있다.

 

다음과 같이 초록색 공간에 장애물을 배치하면 곰곰이와 치킨을 완전히 분리할 수 있다.

 

조금 조심해야되는 부분을 찝어준다면

 

외각부분은 다음과 같이 되므로 예외처리해야한다.

필자는 이 부분때문에 틀렸습니다 를 받았다. ㅠㅠ

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const float INF = 1e10;
const int Dic[8][2] = { {0,1},{0,-1},{1,0},{-1,0} ,{1,1},{-1,-1},{1,-1},{-1,1} };

//////////////////////////////////////////////////////////////////////// 

int N, M;
int MAP[2005][2005];

bool ZeroCheck()
{
	vector<vector<bool>> Visit(N, vector<bool>(M, false));

	queue<pair<int, int>> Q;
	Q.push({ 0,0 });
	Visit[0][0] = true;

	while (Q.empty() == false)
	{
		pair<int, int> now = Q.front();
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ar = now.first + Dic[i][0];
			int ac = now.second + Dic[i][1];
			if (ar < 0 || ac < 0 || ar >= N || ac >= M)
				continue;
			if (MAP[ar][ac] == 1)
				continue;
			if (Visit[ar][ac])
				continue;
			Q.push({ ar, ac });
			Visit[ar][ac] = true;
		}
	}

	return (Visit[N - 1][M - 1] == false);
}

bool OneCheck()
{
	vector<vector<int>> Visit(N, vector<int>(M, 0));

	{
		queue<pair<int, int>> Q1;
		for (int i = 0; i < N; i++)
			if (MAP[i][0] == 1)
			{
				Q1.push({ i,0 });
				Visit[i][0] = 1;
			}
		for (int i = 0; i < M; i++)
			if (MAP[N - 1][i] == 1)
			{
				Q1.push({ N - 1,i });
				Visit[N - 1][i] = 1;
			}


		while (Q1.empty() == false)
		{
			pair<int, int> now = Q1.front();
			Q1.pop();

			for (int i = 0; i < 8; i++)
			{
				int ar = now.first + Dic[i][0];
				int ac = now.second + Dic[i][1];
				if (ar < 0 || ac < 0 || ar >= N || ac >= M)
					continue;
				if (MAP[ar][ac] == 0)
					continue;
				if (Visit[ar][ac] > 0)
					continue;
				Q1.push({ ar, ac });
				Visit[ar][ac] = 1;
			}
		}
	}

	{
		queue<pair<int, int>> Q2;
		for (int i = 0; i < M; i++)
			if (MAP[0][i] == 1)
			{
				Q2.push({ 0,i });
				Visit[0][i] = 2;
			}
		for (int i = 0; i < N; i++)
			if (MAP[i][M - 1] == 1)
			{
				Q2.push({ i,M - 1 });
				Visit[i][M - 1] = 2;
			}


		while (Q2.empty() == false)
		{
			pair<int, int> now = Q2.front();
			Q2.pop();

			for (int i = 0; i < 8; i++)
			{
				int ar = now.first + Dic[i][0];
				int ac = now.second + Dic[i][1];
				if (ar < 0 || ac < 0 || ar >= N || ac >= M)
					continue;
				if (MAP[ar][ac] == 0)
					continue;
				if (Visit[ar][ac] > 0)
					continue;
				Q2.push({ ar, ac });
				Visit[ar][ac] = 2;
			}
		}
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			if (i == 0 && j == 0)
				continue;
			if (i == N - 1 && j == M - 1)
				continue;
			if (MAP[i][j] != 0)
				continue;
			bool one = false;
			bool two = false;
			for (int k = 0; k < 8; k++)
			{
				int ai = i + Dic[k][0];
				int aj = j + Dic[k][1];
				if (ai < 0 || aj < 0 || ai >= N || aj >= M)
				{
					if (ai < 0)
						two = true;
					if (ai >= N)
						one = true;
					if (aj < 0)
						one = true;
					if (aj >= M)
						two = true;
					continue;
				}
				if (Visit[ai][aj] == 1)
					one = true;
				if (Visit[ai][aj] == 2)
					two = true;
			}

			if (one && two)
				return true;
		}
	return false;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			std::cin >> MAP[i][j];

	if (ZeroCheck())
	{
		std::cout << "0" << endl;
		return 0;
	}

	if (OneCheck())
	{
		std::cout << "1" << endl;
		return 0;
	}

	std::cout << "2" << endl;
	return 0;
}