[백준][3197][c++] 백조의 호수

백조의 호수 문제링크

[풀이]
1. 백조끼리 만날 수 있는지 확인
2. 만날 수 있으면 끝
3. 만날 수 없으면 빙판 녹이고
4. 1-3 반복

백조끼리 만날 수 있는지, 빙판 녹이는 거 둘 다 BFS를 이용하면 될 것이라고 생각했는데 R,C가 1500으로 시간 초과가 나게 된다.
이를 해결하기 위해서는 BFS가 level을 기준으로 expand된다는 것을 이용해서 탐색한 데 까지는 저장해두고 다음 call에서 intial points가 되도록 했다.

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <set>
#define N_MAX 1501

using namespace std;

int R, C;
int answer = 0;
pair<int, int> baekjo1, baekjo2;
char Lake[N_MAX][N_MAX];
int dir_y[4] = { 0,0,1,-1 };
int dir_x[4] = { 1,-1,0,0 };
set<pair<int, int>> iceberg;
bool baekjo_visited[N_MAX][N_MAX] = { false, };
queue<pair<int, int>> baekjo_q;   //initial points모아두는 곳이자 BFS에서 사용하는 전형적인 queue
queue<pair<int, int>> baekjo_nq;  //다음 탐색 point 모두 두는 곳
queue<pair<int, int>> iceberg_q;  //initial points모아두는 곳이자 BFS에서 사용하는 전형적인 queue
queue<pair<int, int>> iceberg_nq; //다음 탐색 point 모두 두는 곳


void melt_iceberg() {
	while (!iceberg_q.empty()) {
		pair<int, int> cur = iceberg_q.front();
		iceberg_q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int new_y = cur.first + dir_y[dir];
			int new_x = cur.second + dir_x[dir];

			if (new_x < 0 || new_x >= C || new_y < 0 || new_y >= R) continue;
			if (Lake[new_y][new_x] == 'X') {
				//물 옆에 있는 곳이 빙산이라는 뜻이므로 녹이기 그리고 다음 탐색 point로 저장하기
				iceberg_nq.push(make_pair(new_y, new_x));
				Lake[new_y][new_x] = '.';
			}

		}
	}
}

bool go_baekjo() {
	while (!baekjo_q.empty()) {
		pair<int, int> cur = baekjo_q.front();
		baekjo_q.pop();
		if (cur == baekjo2) {
			return true;
		}

		for (int dir = 0; dir < 4; dir++) {
			int new_y = cur.first + dir_y[dir];
			int new_x = cur.second + dir_x[dir];

			if (new_x < 0 || new_x >= C || new_y < 0 || new_y >= R) continue;
			if (baekjo_visited[new_y][new_x]) continue;
			if (Lake[new_y][new_x] == '.') {
				//물임으로 지나갈 수 있음
				baekjo_q.push(make_pair(new_y, new_x));
				baekjo_visited[new_y][new_x] = true;
			}
			else if (Lake[new_y][new_x] == 'X') {
				//빙산임으로 지나갈 수 없고 다음 탐색 point로 저장
				baekjo_nq.push(make_pair(new_y, new_x));
				baekjo_visited[new_y][new_x] = true;
			}
			else if (Lake[new_y][new_x] == 'L') {
				return true;
			}
		}
	}
	return false;
}


void solve() {
	baekjo_q.push(baekjo1);
	baekjo_visited[baekjo1.first][baekjo1.second] = true;
	while (1) {
		bool flag = go_baekjo();  //백조가 서로 만나는지 확인
		if (flag) return;         //서로 만날시 나가기
		baekjo_q = baekjo_nq;     //백조 BFS를 위한 initial point 지정
		while (!baekjo_nq.empty()) baekjo_nq.pop();  //next point들 초기화
		
		melt_iceberg();         //빙산 녹이기
		iceberg_q = iceberg_nq; //빙산 녹이기 BFS위한 initial point 지정
		while (!iceberg_nq.empty()) iceberg_nq.pop(); //next point 들 초기화
		//print_map();
		
		
		answer++;
		
	}
}

int main() {
	cin >> R >> C;
	string row_lake;
	int baekjo_cnt = 0;
	for (int y = 0; y < R; y++) {
		cin >> row_lake;
		for (int x = 0; x < C; x++) {
			Lake[y][x] = row_lake[x];
			if (Lake[y][x] == 'L') {
				baekjo_cnt++;
				if (baekjo_cnt == 2) {
					//두번째 백조 좌표 저장
					baekjo2.first = y;
					baekjo2.second = x;
				}
				else {
					//첫번째 백조 좌표 저장
					baekjo1.first = y;
					baekjo1.second = x;
				}
				
			}
			if (Lake[y][x] != 'X') {
				//물이거나 백조인것은 빙산 녹이는 BFS에서 initial points가 됨
				iceberg_q.push(make_pair(y, x));
			}
		}
	}
	solve();
	
	cout << answer << "\n";
}

[총평]
다음 탐색 point를 저장해 둔다는 아이디어를 내는 것이어려웠다.