백준 3197 백조의 호수 // bfs멈춰는 tempQ, 1차원에서 논리짜라, next경우의수를 나눠서 처리하라, pair Q 클리어하는법

3197번: 백조의 호수 (acmicpc.net)

3197번: 백조의 호수

* 논리짜기

물) . . 다음(next)경우의수 : '.' X L

'.'-> 계속, 입력시 이미큐에넣어놓음, 방문처리도함 -> 처리필요X

'L'->계속, L도 물로간주. 입력시 처리완료. -> 처리필요X

X -> 멈춰

1.tempQ push

2. 방문처리

3. there을 '.'으로 수정.

 

백조) . . 다음(next)경우의수 : '.' X L

'.'-> 계속, Q.push

'L'-> 만날수있음 -> return true

X -> 멈춰

1.tempQ push

※ 백조에서는 a 배열을 건들지말자.

 

* pair Q 클리어하는법

void Qclear(queue<pair<int, int>>& q) {
	queue<pair<int, int>> empty;
	swap(q, empty);
}

 

#include <bits/stdc++.h> 
#define MAX 100000
#define y1 aaaaa

using namespace std;
int ret, cnt;
int n, m,  y1, x1, y2, x2, ny, nx,
dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int visitedS[1504][1504], visitedW[1504][1504];
char a[1504][1504];
queue<pair<int, int>> swanQ,waterQ,swanTemp,waterTemp;

bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < m;
}
void Qclear(queue<pair<int, int>>& q) {
	queue<pair<int, int>> empty;
	swap(q, empty);
}
bool move_swan()
{
	int y, x;
	while (swanQ.size())
	{
		tie(y, x) = swanQ.front(); swanQ.pop();
		for (int i = 0; i < 4; ++i) {
			//1. 범위체크
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!in(ny, nx)) continue;
			if (visitedS[ny][nx]) continue;
			visitedS[ny][nx] = visitedS[y][x]+1;
			if (a[ny][nx] == '.') {
				swanQ.push({ ny,nx });
			}
			else if (a[ny][nx] == 'X') {
				swanTemp.push({ ny,nx });
				//a[ny][nx] = '.'; ???????
			}
			else if (a[ny][nx] == 'L') {
				//swanTemp.push({ ny,nx });
				return true;
			}
		}
	}
	return false;
}

bool melt_water()
{
	int y, x;
	while (waterQ.size())
	{
		tie(y, x) = waterQ.front(); waterQ.pop();
		for (int i = 0; i < 4; ++i) {
			//1. 범위체크
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!in(ny, nx)) continue;
			if (visitedW[ny][nx]) continue;
			/*visitedW[ny][nx] = visitedW[y][x] + 1;
			if (a[ny][nx] == '.'|| a[ny][nx] == 'L') {
				waterQ.push({ ny,nx });
			}*/ 
			//입력시 처리했으므로 불필요. 
			else if (a[ny][nx] == 'X') {
				visitedW[ny][nx] = visitedW[y][x] + 1;
				waterTemp.push({ ny,nx });
				a[ny][nx] = '.';
			}
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;

	bool first = true;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
			if (a[i][j] == '.'|| a[i][j] == 'L') {
				//백조위치도 물이다.
				waterQ.push({ i,j });
				visitedW[i][j] = 1;
			}
			if (first && a[i][j] == 'L') {
				swanQ.push({ i,j });
				visitedS[i][j] = 1;
				first = false;
			}

		}
	}

	while (true) {
//		fill(&visitedL[0][0], & visitedL[0][0] + 1504 * 1504, 0);
		if (move_swan()) break;
		else ret++;
		melt_water();
		waterQ = waterTemp;
		swanQ = swanTemp;
		Qclear(waterTemp);
		Qclear(swanTemp);
	}
	cout << ret;

}
/*
5 17
 */