백조의 호수(BFS 최적화)

- BFS를 사용하는 문제지만 매번 BFS를 처음부터 진행하면 TimeLimit 발생.

- BFS를 사용하면서 갔던 노드에는 재방문하지 않도록 최적화가 필요한 문제.

- 물, 백조 각각 큐를 만들어서 각각 BFS를 진행.

 

- 백조 BFS의 초기값은 두 백조 중 하나의 좌표

- 백조 BFS에서 도달한 X 좌표들은 다음번 백조 BFS를 시작할 위치들임.

- 2차원 bool 배열을 만들어서 백조 BFS에서 방문했던 위치에 대해 따로 기록하고 이미 방문한 좌표는 탐색하지 않음.

- 백조 BFS에서 백조에 도달하면 반복문을 멈추고 해당 카운트값을 리턴.

 

- 물 BFS의 초기값은 입력받았던 .(물)과 L(백조)의 모든 좌표

- 물 BFS에서 도달한 X 좌표들은 .(물)로 바꿔주고 다음번 물 BFS를 시작할 위치들임.

- 물 BFS는 X 좌표에 대해서만 Enqueue를 진행하므로 따로 Visit 배열을 사용할 필요가 없음.

 

- 백조 BFS와 물 BFS를 한 번씩 진행했다면 도달했던 X좌표의 값을 저장한 NextQueue를 사용하여 BFS를 반복

 

- 2차원 배열 3개로 구현했지만 못풀었고 구글링으로 BFS 최적화 정보 찾은후 작성하여서 통과.

 

#include<iostream>
#include<queue>
using namespace std;

int row, column;
char space[1500][1500] = { 0, };
bool visit[1500][1500] = { 0, };
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
pair<int, int> Swan(-1, -1);
queue<pair<int, int>> WaterQ;
queue<pair<int, int>> WaterNQ;
queue<pair<int, int>> SwanQ;
queue<pair<int, int>> SwanNQ;
bool found = false;

void SwanBFS()
{
	while (!SwanQ.empty())
	{
		int x = SwanQ.front().first;
		int y = SwanQ.front().second;
		SwanQ.pop();
		for (int i = 0; i < 4; i++)
		{
			if (0 <= x + dx[i] && x + dx[i] < row && 0 <= y + dy[i] && y + dy[i] < column)
			{
				if (visit[x + dx[i]][y + dy[i]] == false)
				{
					visit[x + dx[i]][y + dy[i]] = true;
					if (space[x + dx[i]][y + dy[i]] == 'L')
					{
						found = true;
						break;
					}
					else if (space[x + dx[i]][y + dy[i]] == 'X')
					{
						SwanNQ.push(pair<int, int>(x + dx[i], y + dy[i]));
					}
					else if (space[x + dx[i]][y + dy[i]] == '.')
					{
						SwanQ.push(pair<int, int>(x + dx[i], y + dy[i]));
					}
				}
			}
		}
	}
}

void WaterBFS()
{
	while (!WaterQ.empty())
	{
		int x = WaterQ.front().first;
		int y = WaterQ.front().second;
		WaterQ.pop();
		for (int i = 0; i < 4; i++)
		{
			if (0 <= x + dx[i] && x + dx[i] < row && 0 <= y + dy[i] && y + dy[i] < column)
			{
				if (space[x + dx[i]][y + dy[i]] == 'X')
				{
					space[x + dx[i]][y + dy[i]] = '.';
					WaterNQ.push(pair<int, int>(x + dx[i], y + dy[i]));
				}
			}
		}
	}
}

int BFS()
{
	// 물queue, 백조queue 2가지를 이용
	// 물과 백조에 대하여 각각 BFS 진행
	// 백조 BFS에서 도달한 X 좌표는 다음 백조 BFS를 시작할 위치
	// 물 BFS로 도달한 X 좌표들은 다음 차례에 녹을 얼음들임
	// 해당 얼음 좌표를 물의 next_queue에 삽입
	// 현재 BFS 진행중인 queue가 모두 비워지면 next_queue로 BFS 진행
	// 큐를 옮기는 해당 과정을 카운트해서 백조 BFS중 백조를 만나게 되면 그 카운트가 답
	int count = 0;

	while (!(WaterQ.empty() && SwanQ.empty()))
	{
		SwanBFS();
		if (found) break;
		WaterBFS();
		count++;
		SwanQ = SwanNQ;
		SwanNQ = queue<pair<int, int>>();
		WaterQ = WaterNQ;
		WaterNQ = queue<pair<int, int>>();
	}

	cout << count << endl;
	return count;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> row >> column;
	for (int r = 0; r < row; r++)
	{
		for (int c = 0; c < column; c++)
		{
			cin >> space[r][c];
			if (space[r][c] != 'X')
			{
				WaterQ.push(pair<int, int>(r, c));
			}
			if (space[r][c] == 'L')
			{
				Swan.first = r;
				Swan.second = c;
			}
		}
	}

	SwanQ.push(Swan);
	visit[Swan.first][Swan.second] = true;

	BFS();
}

 

백준 3197번 문제(https://www.acmicpc.net/problem/3197)