치즈

일단 이 문제 DFS통해서 품.

한 2~3시간 걸렸는데

겉에서 부터 DFS를 돌린다고 겨우 생각이남.

이 상태에서 DFS돌리면 가운데 부분 뚫려있는 부분을 어떻게 처리를 할지 고민이 많이 됬었는데

그냥 겉에서 부터 돌린다는 생각을 하게 되어서 조금 코드가 돌고 돌았지만 어쨋뜬 맞았다..

cpp 내코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 101

int n, m, Time = 0;
int visited[MAX][MAX];
int arr[MAX][MAX];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};

bool Cango(int y, int x)
{
	if (y <= 0 || y >= n - 1 || x <= 0 || x >= m - 1 || arr[y][x] == 1 || arr[y][x] == 2 || visited[y][x])
	{
		if (arr[y][x] == 1) arr[y][x] = 2;
		return false;
	}
	return true;
}

void DFS(int y, int x)
{
	visited[y][x] = true;
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (Cango(ny, nx) == false) continue;
		DFS(ny, nx);
	}
}

void DFS_ALL()
{
	for (int x = 1; x <= m - 2; ++x)
	{
		if (Cango(1, x) == false) continue;
		DFS(1, x);
	}

	for (int x = 1; x <= m - 2; ++x)
	{
		if (Cango(n - 2, x) == false) continue;
		DFS(n - 2, x);
	}

	for (int y = 1; y <= n - 2; ++y)
	{
		if (Cango(y, 1) == false) continue;
		DFS(y, 1);
	}

	for (int y = 1; y <= n - 2; ++y)
	{
		if (Cango(y, m - 2) == false) continue;
		DFS(y, m - 2);
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> arr[i][j];
		}
	}
	int twoCnt = 0, oneCnt = 0;
	int ret;
	bool flag = false;
	for (;; ++Time)
	{
		if (flag) break;
		for (int y = 1; y <= n - 2; ++y)
			for (int x = 1; x <= m - 2; ++x)
				if (arr[y][x] == 1) ++oneCnt;

		DFS_ALL();

		for (int y = 1; y <= n - 2; ++y)
		{
			for (int x = 1; x <= m - 2; ++x)
			{
				if (arr[y][x] == 2)
				{
					++twoCnt; arr[y][x] = 0;
				}
			}
		}

		if (oneCnt == twoCnt)
		{
			ret = oneCnt;
			flag = true;
		}
		
		memset(visited, 0, sizeof(visited));
		twoCnt = 0; oneCnt = 0;
	}

	cout << Time << endl;
	cout << ret << endl;

	return 0;
}

cpp 수업 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 104

int n, m, cnt, cnt2;
int visited[MAX][MAX], arr[MAX][MAX];
int dy[4] = {0, 1, 0, -1}, dx[4] = {-1, 0, 1, 0};
vector <pair<int, int>> v;

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= m || visited[y][x])
	{
		return false;
	}
	return true;
}

void DFS(int y, int x)
{
	visited[y][x] = true;
	if (arr[y][x] == 1)
	{
		v.push_back({y, x});
		return;
	}
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (Cango(ny, nx) == false) continue;
		DFS(ny, nx);
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> arr[i][j];
		}
	}
	while (1)
	{
		cnt2 = 0;
		fill(&visited[0][0], &visited[0][0] + 104 * 104, 0);
		v.clear();
		DFS(0, 0);
		for (pair<int, int> b : v)
		{
			++cnt2;
			arr[b.first][b.second] = 0;
		}
		bool flag = 0;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (arr[i][j] != 0) flag = 1;
			}
		}
		++cnt;
		if (!flag) break;
	}

	cout << cnt << endl;
	cout << cnt2 << endl;

	return 0;
}