[BFS] 연구소

 

예제 입력 1

7 7

2 0 0 0 1 1 0

0 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 0 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

예제 출력 1

27

예제 입력 2

4 6

0 0 0 0 0 0

1 0 0 0 0 2

1 1 1 0 0 2

0 0 0 0 0 2

예제 출력 2

9

예제 입력 3

8 8

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

예제 출력 3

3

 

 

 

 

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

14502번: 연구소

- 벽을 세우는 내용을 제외하면, 시간 복잡도는 O(NM)

- 벽을 세우는 시간 복잡도는 O(NM^3)

- 총 시간복잡도는 O(NM^4) 가 되는데, N과 M의 최대값이 8이므로 가능하다.

 

- 세운 3개의 벽의 위치(a,b,c)중 중복이 있으면 안되는데, b루프에서 a와의 중복을 체크하고 c루프에서 b와의 중복을 처리하는 식으로 구현했는데, 그럴 경우 a와 c가 중복인 경우를 처리하지 못해서 헤맸었음.

 

#include <stdio.h>

constexpr int MAX_SIZE = 9;
constexpr int MAX_QUEUE_SIZE = 1000;

int R, C;

int dR[4] = { -1, 1, 0, 0 };
int dC[4] = { 0, 0, -1, 1 };

inline int MAX(int a, int b)
{
	return a > b ? a : b;
}

enum Const
{
	EMPTY,
	WALL,
	VIRUS
};

class Point
{
public:
	int r;
	int c;

	Point() { r = c = 0; }
	Point(int r, int c) : r(r), c(c) {}

	bool IsInBoundary()
	{
		return (r >= 0) && (r < R) && (c >= 0) && (c < C);
	}
};


class MapClass
{
public:
	int map[MAX_SIZE][MAX_SIZE];
};
MapClass m;

template <typename T>
class Queue
{
private:
	int front;
	int rear;

	T data[MAX_QUEUE_SIZE];

public:
	Queue() { front = rear = 0; }

	void push(T item)
	{
		data[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = data[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool IsEmpty() { return front == rear; }

	void Reset()
	{
		front = rear = 0;
	}
};
Queue<Point> q;

int go(MapClass m, Queue<Point> q)
{

	while (!q.IsEmpty())
	{
		Point now = q.pop();

		for (int i = 0; i < 4; i++)
		{
			Point next(now.r + dR[i], now.c + dC[i]);
			
			if (!next.IsInBoundary()) continue;
			if (m.map[next.r][next.c] != Const::EMPTY) continue;

			m.map[next.r][next.c] = Const::VIRUS;
			q.push(next);
		}
	}

	int result = 0;

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (m.map[i][j] == Const::EMPTY) result++;
		}
	}
	
	return result;
}

int main(void)
{
	int result = 0;

	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			scanf("%d", &m.map[i][j]);

			if (m.map[i][j] == Const::VIRUS)
			{
				Point p(i, j);
				q.push(p);
			}
		}
	}

	for (int aR = 0; aR < R; aR++)
	{
		for (int aC = 0; aC < C; aC++)
		{
			if (m.map[aR][aC] != Const::EMPTY) continue;

			for (int bR = 0; bR < R; bR++)
			{
				for (int bC = 0; bC < C; bC++)
				{
					if (m.map[bR][bC] != Const::EMPTY) continue;

					for (int cR = 0; cR < R; cR++)
					{
						for (int cC = 0; cC < C; cC++)
						{
							if (m.map[cR][cC] != Const::EMPTY) continue;
							
							if (aR == bR && aC == bC) continue;
							if (bR == cR && bC == cC) continue;
							if (aR == cR && aC == cC) continue;

							m.map[aR][aC] = Const::WALL;
							m.map[bR][bC] = Const::WALL;
							m.map[cR][cC] = Const::WALL;

							result = MAX(result, go(m, q));

							m.map[aR][aC] = Const::EMPTY;
							m.map[bR][bC] = Const::EMPTY;
							m.map[cR][cC] = Const::EMPTY;
						}
					}
				}
			}
		}
	}

	printf("%d\n", result);

	return 0;
}