[Baekjoon] 14502번: 연구소

 

 

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

14502번: 연구소

 

---

 

문제 해결 과정

착안

주어지는 연구소 모양에 대하여 백트래킹(backtracking, 퇴각검색) 알고리즘을 통해 빈 공간에 벽 3개를 세우면서, 바이러스 확산 예상 결과를 너비 우선 탐색(breadth-first search, BFS)을 통해 구하고자 하였다.

 

구현

편의상 벽의 개수를 파악하기 쉽도록 세우고자 하는 벽의 번호를 3, 4, 5로 정하여 프로그래밍 하였다.

 

한편 백트래킹 알고리즘에 기반하여 너비 우선 탐색 알고리즘을 수행해야하므로, 가장 처음 상태의 연구소 모양으로 쉽게 되돌릴 수 있도록 처음 바이러스 위치로부터 확산되는 바이러스들을 숫자 6으로 나타내도록 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>

using namespace std;

int Map[8][8];
int N, M;
int Wall = 3;
int MaxSafeArea = 0;

struct Coord
{
	int X;
	int Y;
};

int CountSafeArea()
{
	int count = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (!Map[i][j])
				count++;

	return count;
}

void Propagation()
{
	queue<Coord> q;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (Map[i][j] == 2)
				q.push(Coord{ j, i });

	while (!q.empty())
	{
		Coord coord = q.front();
		q.pop();
		if (Map[coord.Y][coord.X] == 0)
			Map[coord.Y][coord.X] = 6;

		if (coord.X < M - 1 && !Map[coord.Y][coord.X + 1]) q.push(Coord{ coord.X + 1, coord.Y });
		if (coord.Y < N - 1 && !Map[coord.Y + 1][coord.X]) q.push(Coord{ coord.X, coord.Y + 1 });
		if (coord.X > 0 && !Map[coord.Y][coord.X - 1]) q.push(Coord{ coord.X - 1, coord.Y });
		if (coord.Y > 0 && !Map[coord.Y - 1][coord.X]) q.push(Coord{ coord.X, coord.Y - 1 });
	}

	int safeArea = CountSafeArea();
	if (MaxSafeArea < safeArea)
		MaxSafeArea = safeArea;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (Map[i][j] == 6)
				Map[i][j] = 0;
}

void Backtracking(int x, int y)
{
	if (Map[y][x])
		return;

	Map[y][x] = Wall++;

	if (Wall < 6)
	{
		for (int i = y; i < N; i++)
			for (int j = 0; j < M; j++)
			{
				if (i == y)
					if (j <= x)
						continue;

				Backtracking(j, i);
			}
	}

	if (Wall == 6)
		Propagation();

	Map[y][x] = 0;
	Wall--;
}

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

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

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			Backtracking(j, i);

	cout << MaxSafeArea << "\n";
	return 0;
}

 

실행 결과