[BOJ] 3197. 백조의 호수

문제 원본 : https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int R, C;
char lake[1500][1500];
bool checked[1500][1500];
queue<pair<int, int>> q;
pair<int, int> swan;
queue<pair<int, int>> swanQ;
bool swanChecked[1500][1500];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> R >> C;
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			cin >> lake[i][j];
			if (lake[i][j] == 'L') {
				swan = make_pair(i, j);
			}

			if (checked[i][j] == false && j > 0 && lake[i][j] == 'X' && (lake[i][j - 1] == '.' || lake[i][j - 1] == 'L')) {
				q.push(make_pair(i, j));
				checked[i][j] = true;
			}

			if (j > 0 && checked[i][j - 1] == false && (lake[i][j] == '.' || lake[i][j] == 'L') && lake[i][j - 1] == 'X') {
				q.push(make_pair(i, j - 1));
				checked[i][j - 1] = true;
			}

			if (checked[i][j] == false && i > 0 && lake[i][j] == 'X' && (lake[i - 1][j] == '.' || lake[i - 1][j] == 'L')) {
				q.push(make_pair(i, j));
				checked[i][j] = true;
			}

			if (i > 0 && checked[i - 1][j] == false && (lake[i][j] == '.' || lake[i][j] == 'L') && lake[i - 1][j] == 'X') {
				q.push(make_pair(i - 1, j));
				checked[i - 1][j] = true;
			}
		}
	}

	swanQ.push(swan);
	swanChecked[swan.first][swan.second] = true;

	int cnt = 0;
	while (true) {
		queue<pair<int, int>> buf;
		queue<pair<int, int>> swanBuf;

		while (!swanQ.empty()) {
			int r = swanQ.front().first;
			int c = swanQ.front().second;
			swanQ.pop();

			for (int i = 0; i < 4; ++i) {
				int nr = r + dir[i][0];
				int nc = c + dir[i][1];

				if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
					continue;
				}

				if (swanChecked[nr][nc] == false && lake[nr][nc] == 'L') {
					cout << cnt << "\n";
					return 0;
				}

				if (swanChecked[nr][nc] == false && lake[nr][nc] == '.') {
					swanQ.push(make_pair(nr, nc));
					swanChecked[nr][nc] = true;
				}

				if (swanChecked[nr][nc] == false && lake[nr][nc] == 'X') {
					swanBuf.push(make_pair(nr, nc));
					swanChecked[nr][nc] = true;
				}
			}
		}

		while (!q.empty()) {
			int r = q.front().first;
			int c = q.front().second;
			q.pop();
			lake[r][c] = '.';

			for (int i = 0; i < 4; ++i) {
				int nr = r + dir[i][0];
				int nc = c + dir[i][1];

				if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
					continue;
				}

				if (checked[nr][nc] == false && lake[nr][nc] == 'X') {
					buf.push(make_pair(nr, nc));
					checked[nr][nc] = true;
				}
			}
		}

		++cnt;
		q = buf;
		swanQ = swanBuf;
	}
}

 

• 전체를 BFS 돌리면 시간초과가 나기 때문에 처음에 녹을 좌표만 큐에 넣고 만날 때까지 BFS 반복
• 반복 BFS 돌릴 때도 다음에 녹을 좌표만 큐에 삽입