[BOJ] 백준 3197번 : 백조의 호수 C++ : 아주정은

이 문제는 처음에 다른 BFS문제와 비슷하게 풀이를 생각하였다.

L과 L사이에 길이 있는지 없는지 판단한다.

길이 없을 경우 얼음을 녹이고, 다시 길을 있는지 판단한다.

백조 두마리는 항상 존재하고 얼음이 녹으면 길이 존재하기에 반복문을 통해서 길을 찾을때까지 반복하면 답은 나온다.

문제는 시간초과이다.

처음에는 무식하게 BFS로 L부터 L까지의 길을 찾으려고 했다. 그랬더니 시간초과가 떴지모얌...

생각을 해볼려다가....솔직하게 구글에 백준 3197번 검색^^

꾸준함님꺼 참고해서 풀었다. 여러가지 방법이 있지만, 내가 아는 방법을 설명해보겠다.

시간초과가 나는 이유는 L부터 L까지 갈려고할때 BFS로 계속 하면 시간초과가 발생한다. 1500x1500이기 때문이다.

솔직히 시간복잡도 계산은 잘못한다. 그래서 처음에 둘중에 하나의 L이 주변에 있는 물을 싹 둘러본다. BFS로.

그러면 거기에 L이 없다고 판단되면 물옆에 얼음은 시간이 지나면 녹겠지? 그것을 nextQ에 넣는다.

그리고 얼음들을 녹여준다.

그니깐 nextQ에는 L이 다음에 둘러볼 물만 남는것이다. 가릿? 전에 물은 방문했으니깐 안가도된다~ 이말이야

이게 키포인트이다.

그리고 얼음 녹이는 것도, 나는 for문 두개써서 다 돌면서 빙산인데 옆에 물이면 녹인다. 이렇게 판단했었다.

근데 지금은 waterQ라는 것을 생성해서 처음에 물인 곳을 다 때려박고, 그 다음 옆에 얼음인것을 녹여주는 방식을 선택했다.

아무쪼록 주옥같아서 여러번 풀어봐야할 문제이다.

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int y;
};

char board[1501][1501];
bool vis[1501][1501];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

int main()
{
	int R, C;
	int lx, ly;
	string str;
	int time = 0;

	queue<Que> waterQ;
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		cin >> str;
		for (int j = 0; j < C; j++) {
			board[i][j] = str[j];
			if (board[i][j] == 'L') {
				lx = i;
				ly = j;//L위치
			}//나중에 입력된 L의 위치가 저장된다.
			if (board[i][j] == '.' or board[i][j] == 'L') {
				waterQ.push({ i,j });
			}
		}
	}

	queue<Que> Q;
	Q.push({ lx,ly });
	vis[lx][ly] = true;

	while (1) {
		queue<Que> nextQ;
		bool suc = false;
		while (!Q.empty() and !suc) {
			auto cur = Q.front();
			Q.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx<0 or nx>R - 1 or ny<0 or ny>C - 1)continue;
				
				if (board[nx][ny] == 'L' and vis[nx][ny] == false) {
					suc = true;
					break;
				}//다른백조 만나면 성공
				if (board[nx][ny] == '.' and vis[nx][ny] == false) {
					Q.push({ nx,ny });
					vis[nx][ny] = true;
				}//물인데 방문한적없으면 큐에 넣는다.
				if (board[nx][ny] == 'X' and vis[nx][ny] == false) {
					nextQ.push({ nx,ny });
					vis[nx][ny] = true;
				}//물옆에 있는 얼음이면 다음에 방문할것이다.
			}
		}
		if (suc) {
			cout << time << endl;
			break;
		}
		Q = nextQ;

		int watersize = waterQ.size();

		while (watersize--) {
			auto cur = waterQ.front();
			waterQ.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (nx<0 or nx>R - 1 or ny<0 or ny>C - 1)continue;
				if (board[nx][ny] == 'X') {
					waterQ.push({ nx,ny });
					board[nx][ny] = '.';
				}
			}
		}
		time++;

	}
}