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

백준 3197

🌲 문제 요약

빙판이 덮여 있는 호수 위에 두 마리의 백조가 있을 때, 이들이 며칠이 지나야 서로 만날 수 있는지 계산하는 문제.

🌲 문제 풀이

백조와 물의 위치 정보를 각각 visited_swan, swanQ 와 visited, waterQ에 담은 후, while문 반복을 통해 하루가 지날 때마다 호수에 나타나는 변화를 확인한다. 이때, swan_tmpQ와 water_tmpQ는 직전 반복의 상황을 기록하는 역할을 하며, while문은 두 마리의 백조가 만나는 날에 break한다.

🌲 주의

백조의 위치 또한 물 공간으로 간주해야 하므로, 처음 물의 위치 정보를 저장하는 과정에서 if (a[i][j] == '.' || a[i][j] == 'L')를 else if (a[i][j] == '.' || a[i][j] == 'L')로 쓰지 않도록 주의한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int r, c, day, y, x, swanY, swanX, visited[1505][1505], visited_swan[1505][1505];
char a[1505][1505];
queue<pair<int, int>> swanQ, swan_tmpQ, waterQ, water_tmpQ;

bool swan_moving() {
	while (swanQ.size()) {
		tie(y, x) = swanQ.front(); swanQ.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
			if (visited_swan[ny][nx]) continue;
			visited_swan[ny][nx] = 1;
			if (a[ny][nx] == '.') {
				swanQ.push({ny, nx});
			}
			else if (a[ny][nx] == 'X') {
				swan_tmpQ.push({ny, nx});
			}
			else return true;
		}
	}
	return false;
}

void water_melting() {
	while (waterQ.size()) {
		tie(y, x) = waterQ.front(); waterQ.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
			if (visited[ny][nx]) continue;
			if (a[ny][nx] = 'X') {
				a[ny][nx] = '.';
				visited[ny][nx] = 1;
				water_tmpQ.push({ny, nx});
			}
		}
	}
	return;
}

void toZero(queue<pair<int, int>> &q) {
	queue<pair<int, int>> tmp;
	swap(q, tmp);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'L') {
				swanY = i; swanX = j;
			}
			if (a[i][j] == '.' || a[i][j] == 'L') {
				visited[i][j] = 1;
				waterQ.push({i, j});
			}
		}
	}
	visited_swan[swanY][swanX] = 1;
	swanQ.push({swanY, swanX});
	
	while (1) {
		if (swan_moving()) break;
		water_melting();
		swanQ = swan_tmpQ;
		waterQ = water_tmpQ;
		toZero(swan_tmpQ);
		toZero(water_tmpQ);
		day++;
	}
	cout << day << '\n';
	
	return 0;
}