[BFS ] 벽 부수고 이동하기 4

예제 입력 1

3 3

101

010

101

예제 출력 1

303

050

303

예제 입력 2

4 5

11001

00111

01010

10101

예제 출력 2

46003

00732

06040

50403

 

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

16946번: 벽 부수고 이동하기 4

 

- 만약, 이 문제를 고전적인 방법 맵을 탐색하면서 벽이면 부수고 BFS돌고 다시 원상복구 하는 식을 반복하여 풀면 시간복잡도는 O(NM) * O(NM) = O(NM^2) 이다. (N x M 맵 탐색하면서 벽이면 부수는거 = O(NM), BFS = O(NM)) 

N,M 제한이 1000이므로 시간 복잡도 상으로 풀수 없다.

 

- 따라서, 일단 각각의 빈칸에서 이동할 수 있는 부분을 그룹으로 묶고 그 그룹의 개수를 센다. (그 그룹 간에 이동할 수 있는 칸이 나온다.)

- 이 예시에서,

1번 그룹 내에서 이동할 수 있는 칸의 수는 7

2번 그룹 내에서 이동할 수 있는 칸의 수는 1

3번 그룹 내에서 이동할 수 있는 칸의 수는 7이다.

 

위의 빨간 칸은 벽인데 이를 부수고 이동할 수 있는 칸의 수는 1번 그룹과 3번 그룹과 인접하므로 ,

= 1번 그룹 개수 7개 + 3번 그룹 개수 7개 + 자기자신 1개 = 총 15개가 된다. 

 

이런식으로 풀어나간다.

 

// 이 규칙을 적용할 때, 그룹의 개수가 몇개가 될지 모르는데, 중복 카운트를 효율적으로 방지하기 위해 set을 사용함.

#include <stdio.h>
#include <set>

constexpr int MAX_QUEUE_SIZE = 10000;
constexpr int MAX_SIZE = 1001;
constexpr int MAX_GROUP_SIZE = 1001 * 1000;

int map[MAX_SIZE][MAX_SIZE];
int group[MAX_SIZE][MAX_SIZE];
int groupCounter[MAX_GROUP_SIZE];

int R, C;

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

class Point
{
public:
	int r;
	int c;

	Point() { r = c = 0; }

	Point(int r, int c) : r(r), c(c) {}

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

template <typename T>
class Queue
{
public:
	int front;
	int rear;
	T data[MAX_QUEUE_SIZE];

	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; }
};
Queue<Point> q;

void BFS(int r, int c, int groupNum)
{
	int counter = 1;

	Point now(r, c);
	group[r][c] = groupNum;
	q.push(now);

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

		for (int i = 0; i < 4; i++)
		{
			Point nextPoint(now.r + dR[i], now.c + dC[i]);

			if (!nextPoint.isInBoundary(R, C)) continue;

			if (group[nextPoint.r][nextPoint.c] == 0 && map[nextPoint.r][nextPoint.c] == 0)
			{
				group[nextPoint.r][nextPoint.c] = groupNum;
				counter++;
				q.push(nextPoint);
			}
		}
	}

	groupCounter[groupNum] = counter;
}

int main(void)
{
	scanf("%d %d", &R, &C);

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

	int groupNumber = 1;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (group[i][j] == 0 && map[i][j] == 0) // 방문하지 않은 곳
			{
				BFS(i, j, groupNumber);
				groupNumber++;
			}
		}
	}

	// 벽이 빈칸이 될때 갈수있는칸 = 상하좌우 방향으로 인접한 그룹들의 연결된 칸의 합(그룹 중복 X)
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (map[i][j] == 0)
			{
				printf("0");
			}
			else
			{
				int result = 0;

				std::set<int> counter; // 상하좌우 검사할 때 중복되어 들어가지 않도록
				for (int k = 0; k < 4; k++)
				{
					Point next(i + dR[k], j + dC[k]);

					if (!next.isInBoundary(R, C)) continue;
					counter.insert(group[next.r][next.c]);
				}

				for (int item : counter)
				{
					result = (result + groupCounter[item]) % 10;
				}

				printf("%d", (result + 1) % 10); // 자기 자신. 여기서도 % 10 해줘야함에 유의
			}
		}
		printf("\n");
	}
	printf("\n");

	return 0;
}