연구소 - 14502

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

14502번: 연구소

 

코드 : 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;
int num[8][8] = { 0 };
int temp[8][8] = { 0 };
vector<std::pair<int, int>> virusArr;
queue<std::pair<int, int>> virusRoute;
int mv[4][2] = { 
	{-1, 0},
	{0,-1},
	{0,1},
	{1,0}
};
int totalCount = 0;

void ArrayCopy(int num[][8], int temp[][8])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			temp[i][j] = num[i][j];
		}
	}
}

void VirusFlowBFS(int arr[][8])
{
	while (virusRoute.size() != 0)
	{
		auto v = virusRoute.front();
		virusRoute.pop();

		for (int i = 0; i < 4; i++)
		{
			int n = v.first + mv[i][0];
			int m = v.second + mv[i][1];

			if ((n >= 0 && n < N) && (m >= 0 && m < M))
			{
				if (arr[n][m] == 0)
				{
					arr[n][m] = 2;
					virusRoute.push(std::pair<int, int>(n, m));
				}
			}
		}
	}
}

void CheckSafe(int arr[][8])
{
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] == 0)
			{
				count++;
			}
		}
	}
	if (totalCount < count)
	{
		/*for (int i = 0; i < N; i++)
		{
			for (int j = 0; j <M; j++)
			{
				cout << arr[i][j];

			}
			cout << "\n";
		}*/
		totalCount = count;
	}
}

void MakeWall(int count, int n, int m)
{
	if (count >= 3)
	{
		int temp2[8][8];
		ArrayCopy(temp, temp2);
		for (int i=0; i < virusArr.size(); i++)
		{
			virusRoute.push(virusArr[i]);
		}
		//바이러스 퍼트리기
		VirusFlowBFS(temp2);
		//0의 갯수 파악
		CheckSafe(temp2);
		return;
	}
	//벽 세우기
	for (int i = n; i < N; i++, m = 0)
	{
		for (int j = m; j < M; j++)
		{
			if (temp[i][j] == 0)
			{
				temp[i][j] = 1;
				MakeWall(count + 1, i, j+ 1);
				temp[i][j] = 0;
			}
			
		}
	}
}

void Solution()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (num[i][j] == 0)
			{
				//초기값으로 초기화
				ArrayCopy(num, temp);
				MakeWall(0, i, j);
			}
		}
	}
}

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

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> num[i][j];
			//바이러스 시작지점 저장
			if (num[i][j] == 2)
			{
				virusArr.push_back(std::pair<int, int>(i, j));
			}
		}
	}
	Solution();
	cout << totalCount << "\n";
	return 0;
}

이문제부터 내가 문제를 풀때 좀 더 효율적으로 풀 수 있도록 5가지 순서를 만들어보았다. (여기)

해서 해당문제부터는 5가지 순서를 지키면서 풀어보려고 했다.

1. 조건파악 (10분)
2. 방향설정(5분) : 벽을 세우는 처리 -> 바이러스 퍼트리기 -> 0의 갯수파악 -> 크기비교 후 저장
3. 알고리즘 선택(20분) : DFS -> BFS -> Loop -> if 
4.  코드 구현(50분)
5. 검증 (5분)

시간은 대략적으로 작성한 것이다. 다음부터 작성할 것 은 제대로 시간을 측정하면서 풀어볼 생각이다.