Boj 3197) Labudovi

문제

백준 3197

설명

핵심 테크닉이 2개가 있음.

1. L 에서 L 을 찾아가는 BFS q1 과, X 를 없애는 BFS q2 를 총 한번만 수행함.
2. X 를 없앤 좌표를 q1 에서 방문했었다면 그대로 q1 대기열에 집어넣음

혹은 queue 를 4개를 둬서 BFS 에서 막힌 구간만 기억해놓을 수 있음.

• 하지만 이러면 기억해놓은 queue 의 내용을 탐색용 queue 에 복사해야 해서 느림.
• 또한 중복되는 좌표가 들어가는 경우 TLE 가 뜰 수 있음

혹은 UnionFind 로 풀수도 있음

• 크게 느리진 않는데 BFS 보단 느림.

queue 대신 array 를 쓰면 시간이 미비하게 조금은 줄어듬. ( 92ms -> 80ms)

시간 복잡도

O(\(4RC\))

코드

const int MAX_IN = 1501 * 1501;
char board[MAX_IN]; // 2250000
int r, c;
int L1 = -1, L2 = -1;

bool visitTB[MAX_IN];
queue<int, vector<int>> q_water, q_bfs;

void MeltPush(int cur)
{
	board[cur] = '.';
	q_water.push(cur);
	if (visitTB[cur])
		q_bfs.push(cur);  // 핵심
}

void Melt()
{
	int size = q_water.size();
	while (size--)
	{
		int cur = q_water.front(); q_water.pop();
		int x = cur % c, y = cur / c;
		if (x > 0 && board[cur - 1] == 'X')      MeltPush(cur - 1);
		if (x + 1 < c && board[cur + 1] == 'X')  MeltPush(cur + 1);
		if (y > 0 && board[cur - c] == 'X')      MeltPush(cur - c);
		if (y + 1 < r && board[cur + c] == 'X')  MeltPush(cur + c);
	}
}

inline void Push(int cur)
{
	if (visitTB[cur]) return;
	visitTB[cur] = true;

	if (board[cur] == 'X') return;
	q_bfs.push(cur);
}

bool BFS()
{
	while (!q_bfs.empty())
	{
		int cur = q_bfs.front(); q_bfs.pop();
		if (cur == L2) return true;

		int x = cur % c; int y = cur / c;
		if (x > 0)     Push(cur - 1);
		if (x + 1 < c) Push(cur + 1);
		if (y > 0)     Push(cur - c);
		if (y + 1 < r) Push(cur + c);
	}
	
	return false;
}


int main()
{
	cin >> r >> c;

	for (int i = 0; i < r * c; i++)
	{
		cin >> board[i];
		if (board[i] != 'X')
		{
			q_water.push(i);
			if (board[i] == 'L') {
				if (L1 == -1) { L1 = i;  q_bfs.push(i); }
				else L2 = i;
			}
		}
	}
	
	int ans = 0;
	while (!BFS())
	{
		Melt();
		ans++;
	}
	
	cout << ans;
}