백조의 호수 (feat. 백준, 3197번)

백조의 호수
https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int R, C, dx[4], dy[4];
bool visit[1501][1501];
char arr[1501][1501];
queue<pair<int, int>> nq, q, water, swan;
bool bfs() {
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		register int x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < R && 0 <= ny && ny < C && !visit[nx][ny]) {
				visit[nx][ny] = true;
				if (nx == swan.front().first && ny == swan.front().second)
					return true;
				if (arr[nx][ny] == '.')			// 녹은 곳이면
					q.push(make_pair(nx, ny));
				else if (arr[nx][ny] == 'X')
					nq.push(make_pair(nx, ny));
			}
		}
	}
	return false;
}
void melt() {
	register int len = water.size();
	while (len--) {
		auto p = water.front(); water.pop();
		register int x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < R && 0 <= ny && ny < C && arr[nx][ny] == 'X')	// 주변에 얼음이 있으면
				arr[nx][ny] = '.', water.push(make_pair(nx, ny));		// 물로 변하고 다음번 주변 얼음을 체크
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> R >> C;
	for(register int r = 0, c; r < R; ++r)
		for (c = 0; c < C; ++c) {
			cin >> arr[r][c];
			if (arr[r][c] == 'L')
				swan.push(make_pair(r, c)), arr[r][c] == '.', water.push(make_pair(r, c));
			else if (arr[r][c] == '.')
				water.push(make_pair(r, c));
		}
	
	memset(visit, false, sizeof(visit));
	visit[swan.front().first][swan.front().second] = true;
	q.push(swan.front()), swan.pop();
	register int ans = 0;
	while (1) {
		if (bfs())
			break;
		melt();
		++ans;
		q.swap(nq);
	}
	cout << ans;
	return 0;
}
// *&)*@*

1. 모든 물 ('.') 위치를 저장합니다.
2. 아무 백조나 선택하여 bfs를 진행합니다. 진행중 얼음 ('X')은 모두 저장합니다.
3. bfs가 끝나도 다른 백조를 만나지 못햇다면, 1번에서 저장했던 모든 물을 검사하여 상,하,좌,우 중 얼음이 있다면 녹여줍니다. 
4. 그리고 다음 2번은 이전 얼음으로 저장했던 큐를 사용합니다. 왜냐하면 이전의 얼음이 있던 위치가 다음번 시작 지점이기 때문입니다.