백준 14502번 연구소 (C++)

문제

정답 코드

#include <stack>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <utility>
using namespace std;

const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int n,m;

int do_find(vector<vector<int>> to_find)
{//맵이 고정됐으니까 이제 각 값들에 대해서 안전영역이 몇개인지 찾기.
	vector vis(n,vector<int>(m,0));
	for (int i=0;i < n; i++)
	{
		for (int j =0;j < m;j++)
		{
			if (to_find[i][j] == 2 && vis[i][j] == 0)
			{
				vis[i][j] = 1;
				queue<pair<int,int>> Q;
				Q.push({i,j});//y,x
				while (!Q.empty())
				{
					pair<int,int> p = Q.front();
					Q.pop();
					for (int k=0;k < 4;k++)
					{
						if (p.first + dy[k]< 0 ||  p.second + dx[k] < 0 || p.first + dy[k] >= n || p.second + dx[k] >=m)
							continue;
						if (vis[p.first + dy[k]][p.second + dx[k]] == 1 || to_find[p.first + dy[k]][p.second + dx[k]] == 1)
							continue ;
						vis[p.first + dy[k]][p.second + dx[k]] = 1;
						to_find[p.first + dy[k]][p.second + dx[k]] = 2;
						Q.push({p.first + dy[k],p.second + dx[k]});
					}
				}
			}
		}
	}
	//bfs를 완료해서 현재 맵에서 2가 인접한 부분들은 전부 다 2로 바뀜
	// 이제 총 0의 갯수를 세서 리턴
	int cnt =0;
	for (int i=0;i < n;i++)
	{
		for (int j=0;j < m; j++)
		{
			if (to_find[i][j] == 0)
				cnt++;
		}
	}
	return (cnt);
}

int map_change(vector<vector<int>> to_find)
{
	int ret =0;
	int max = 0;
	for (int i=0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			if (to_find[i][j] == 0)
			{//1번 잡아두고
				to_find[i][j] = 1;
				for (int b1 = 0; b1 <n; b1++)
				{
					for(int b2 = 0;b2 < m;b2++)
					{
						if (to_find[b1][b2] == 0)
						{//2번 잡아두고
							to_find[b1][b2] = 1;
							for(int c1 = 0;c1 < n; c1++)
							{
								for (int c2 = 0; c2 < m; c2++)
								{// 3번 잡아두고
									if (to_find[c1][c2] == 0)
									{//3번까지 잡았으면
										to_find[c1][c2] = 1;
										ret = do_find(to_find);
										if (max < ret)
											max = ret;
										to_find[c1][c2] = 0;
									}
								}
							}
							to_find[b1][b2] = 0;
						}
					}
				}
				to_find[i][j] = 0;
			}
		}
	}
	return (max);
}

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

	cin >> n >> m;
	vector arr(n + 1,vector<int>(m + 1,0));
	for (int i=0;i < n;i++)
	{
		for (int j=0;j < m;j++)
		{
			cin >> arr[i][j];
		}
	}
	cout << map_change(arr);
}
/*

1 2 1 1
1 0 1 2
1 0 0 0
2 0 0 0

*/

문제 풀이의 흐름

• 이 문제는 전체 탐색을 하면 편하다.

• 배열을 선언해서 입력을 쭉 받고

• 맵을 계속 바꿔주고 즉 세개의 벽을 세우는 모든 경우에 수를 하면서

• 각 경우에 대해서 경우를 출력하면 결과 값이 나온다.

주의 할 점

• 이 문제에서 쓸때없이 조건문을 추가해줘서 자꾸 왜 틀린지 모르는 틀린 값이 나왔는데

• 아직도 저 조건문이 어떤 부분을 틀리게 하는지는 모르겠다.

• 왠만하면 시간 복잡도의 여유가 있다면 쓸때없는 조건문을 줄여보자.

반성 및 고찰

틀린코드…

#include <stack>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <utility>
using namespace std;

const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int n,m;

int do_find(vector<vector<int>> to_find)
{//맵이 고정됐으니까 이제 각 값들에 대해서 안전영역이 몇개인지 찾기.
	vector vis(n+1,vector<int>(m + 1,0));
	for (int i=0;i < n; i++)
	{
		for (int j =0;j < m;j++)
		{
			if (to_find[i][j] == 2 && vis[i][j] == 0)
			{
				vis[i][j] = 1;
				queue<pair<int,int>> Q;
				Q.push({i,j});//y,x
				while (!Q.empty())
				{
					pair<int,int> p = Q.front();
					Q.pop();
					for (int k=0;k < 4;k++)
					{
						if (p.first + dy[k]< 0 ||  p.second + dx[k] < 0 || p.first + dy[k] >= n || p.second + dx[k] >=m)
							continue;
						if (vis[p.first + dy[k]][p.second + dx[k]] == 1 || to_find[p.first + dy[k]][p.second + dx[k]] == 1)
							continue ;
						vis[p.first + dy[k]][p.second + dx[k]] = 1;
						to_find[p.first + dy[k]][p.second + dx[k]] = 2;
						Q.push({p.first + dy[k],p.second + dx[k]});
					}
				}
			}
		}
	}
	//bfs를 완료해서 현재 맵에서 2가 인접한 부분들은 전부 다 2로 바뀜
	// 이제 총 0의 갯수를 세서 리턴
	int cnt =0;
	for (int i=0;i < n;i++)
	{
		for (int j=0;j < m; j++)
		{
			if (to_find[i][j] == 0)
				cnt++;
		}
	}
	return (cnt);
}

int map_change(vector<vector<int>> to_find)
{
	int ret =0;
	int max = 0;
	for (int i=0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			if (to_find[i][j] == 0)
			{//1번 잡아두고
				to_find[i][j] = 1;
				for (int b1 = i; b1 <n; b1++)
				{
					int b2;
					if (b1 == i)
						b2 = j;
					else
						b2 = 0;
					for( ;b2 < m;b2++)
					{
						if (to_find[b1][b2] == 0)
						{//2번 잡아두고
							to_find[b1][b2] = 1;
							for(int c1 = b1;c1 < n; c1++)
							{
								int c2;
							if (c1 == b1)
								c2 = j;
							else
								c2 = 0;
								for (; c2 < m; c2++)
								{// 3번 잡아두고
									if (to_find[c1][c2] == 0)
									{//3번까지 잡았으면
										to_find[c1][c2] = 1;
										ret = do_find(to_find);
										if (max < ret)
											max = ret;
										to_find[c1][c2] = 0;
									}
								}
							}
							to_find[b1][b2] = 0;
						}
					}
				}
				to_find[i][j] = 0;
			}
		}
	}
	return (max);
}

int main()
{
	// ios:: sync_with_stdio(0);
	// cin.tie(0); cout.tie(0);

	cin >> n >> m;
	vector arr(n + 1,vector<int>(m + 1,0));
	for (int i=0;i < n;i++)
	{
		for (int j=0;j < m;j++)
		{
			cin >> arr[i][j];
		}
	}
	cout << map_change(arr);
}
/*

1 2 1 1
1 0 1 2
1 0 0 0
2 0 0 0

*/

Uploaded by N2T