[백준] 14502 연구소

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

14502번: 연구소

전형적인 dfs, bfs 문제였다.  문제를 읽으며 세로 크기 N 과 가로 크기 M 의 범위가 3~8 사이인 것을 보고 벽이 놓일 수 있는 위치를 모두 구해본 뒤에 그 중 빈칸의 개수가 가장 많은 것을 구해야하는 것임을 알았다. 하지만 벽의 놓이는 경우의 수를 구하는 과정에서 까다로움을 느꼈고,  permutation (순열) 이라는 개념을 이용하였다. 

 

---

이번 문제에서 익힌 개념

 

next_permutation , prev_permutation

벽이 놓이는 경우의 수를 구하기 위해 어떻게 할지 고민하다가 #include <algorithm> 에 있는 next_permutation , prev_permutation 를 알게 되었다. 

 

• next_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.
• prev_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.

예를 들어보자, 1234 의 배열이 있을 경우에는 next_permutation을 하면 그 다음으로 1243으로 바뀌고 함수는 true를 반환한다. 1234 의 배열을 prev_permutation을 하면 이전 순열이 없으므로 false를 반환하고 4321로 돌아간다.

이번 문제에서 쓴 0 과 1로 이루어진 배열에 이 함수를 사용해보자. 만약 배열이 1100 으로 이루어졌을 때 prev_permutation을 사용하면 1010 -> 1001 -> 0110 -> 0101 -> 0011 순으로 이동할 것이고, next_permutation을 사용하면 false 를 반환하고 0011로 이동할 것이다. 

 

copy 함수

배열을 다른 배열에 복사하기 위해 copy 함수를 사용하였다. 원래는 for문을 이용해서 복사하였으나 코드가 너무 길어져서 copy 함수를 이용하였다. 

 

형태는 1차원 배열일때

arr[10]을 temp[10]으로 옮긴다고 하자

그러면 copy(arr, arr+10 , temp) 를 사용하면 된다.

 

다차원 배열일때 

 

arr[10][10] 을 temp[10][10]으로 옮긴다고 할때

copy(&arr[0][0], &arr[0][0]+100, &temp[0][0])를 사용하면 된다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int graph[8][8];
int temp_graph[8][8];
int result;

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

void dfs(int a, int b)
{
	for (int i = 0; i < 4; i++)
	{
		int x = a + dx[i];
		int y = b + dy[i];

		if (x >= 0 && x < N && y >= 0 && y < M)
		{
			if (temp_graph[x][y] == 0)
			{
				temp_graph[x][y] = 3;
				dfs(x, y);
			}

		}
	}
}

int count_zero()
{
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (temp_graph[i][j] == 0)
				cnt++;
		}
	}

	return cnt;
}

int main()
{
	
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> graph[i][j];
		}
	}

	vector<pair<int, int>> empty_arr;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (graph[i][j] == 0)
			{
				empty_arr.push_back({ i,j });
			}
		}
	}

	vector<int> arr(empty_arr.size(), 0);
	arr[0] = 1;
	arr[1] = 1;
	arr[2] = 1;


	do {
		copy(&graph[0][0], &graph[0][0] + 64, &temp_graph[0][0]);
		
		for (int i = 0; i < arr.size(); i++)
		{
			if (arr[i] == 1)
			{
				temp_graph[empty_arr[i].first][empty_arr[i].second] = 1;
			}
		}
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (temp_graph[i][j] == 2)
					dfs(i, j);
			}
		}
		
		result = max(result, count_zero());
	} while (prev_permutation(arr.begin(), arr.end()));


	cout << result;
}

순열의 개념과 배열의 복사 개념을 익힐 수 있는 좋은 문제였다 ㅎㅎ