백조의 호수

https://www.acmicpc.net/problem/3197

문제

두 마리의 백조가 호수에서 살고 있었다.

그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다.

어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다.

두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다.

‘.’은 물 공간, ‘X’는 빙판 공간, ‘L’은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

예제 입력 1

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

예제 출력 1

3

예제 입력 2

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

예제 출력 2

2

예제 입력 3

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

예제 출력 3

2

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #2 – Seniors 2번

• 문제를 번역한 사람: baemin0103
• 데이터를 추가한 사람: dlbae9613

알고리즘 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 분리 집합

통과된 코드

해당 얼음이 언제 녹는지 확인하고 저장합니다.

BFS 탐색을 할 때 목표에 도달하지 못한 생태에서 Queue가 empty라면

날짜를 하루씩 증가시키고 해당 일자에 녹는 얼음을 빈칸으로 변경하고 탐색을 이어나간다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int _R, _C, _DxDy[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<pair<int, int>> _SwanPosV;
vector<pair<int, int>> _IcePosV[750];
queue<pair<int, pair<int, int>>> _IceQueue;
queue<pair<int, int>> _SwanQueue;
char _Map[1501][1501];
bool _isVisted[1501][1501];
string str;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> _R >> _C;

	for (int i = 0; i < _R; i++) {
		cin >> str;
		for (int j = 0; j < _C; j++) {
			_Map[i][j] = str[j];
			if (str[j] == 'L') {
				_SwanPosV.push_back(make_pair(i, j));
				_Map[i][j] = '.';
			}
			else if (str[j] == 'X')
				_IcePosV[0].push_back(make_pair(i, j));
		}
	}

	int _dx, _dy;
	pair<int, int> _Pos;

	for (auto& it : _IcePosV[0]) {
		for (int j = 0; j < 4; j++) {
			_dx = it.first + _DxDy[j][0];
			_dy = it.second + _DxDy[j][1];
			if (_dx >= _R || _dy >= _C || _dx < 0 || _dy < 0)
				continue;
			if (_Map[_dx][_dy] == '.') {
				_IcePosV[1].push_back(it);
				break;
			}
		}
	}

	for (auto& it : _IcePosV[1]) {
		_isVisted[it.first][it.second] = true;
		_IceQueue.push(make_pair(1, it));
	}

	while (!_IceQueue.empty()) {
		_Pos = _IceQueue.front().second;
		int _cnt = _IceQueue.front().first;
		_IceQueue.pop();
		for (int j = 0; j < 4; j++) {
			_dx = _Pos.first + _DxDy[j][0];
			_dy = _Pos.second + _DxDy[j][1];
			if (_dx >= _R || _dy >= _C || _dx < 0 || _dy < 0)
				continue;
			if (_isVisted[_dx][_dy] || _Map[_dx][_dy] != 'X')
				continue;
			_isVisted[_dx][_dy] = true;
			_IceQueue.push(make_pair(_cnt + 1, make_pair(_dx, _dy)));
			_IcePosV[_cnt + 1].push_back(make_pair(_dx, _dy));
		}
	}
	
	for (int i = 0; i < _R; i++)
		for (int j = 0; j < _C; j++)
			_isVisted[i][j] = false;
	
	_SwanQueue.push(_SwanPosV[0]);
	_isVisted[_SwanPosV[0].first][_SwanPosV[0].second] = true;
	_IcePosV[0].clear();
	int _Day = 0;
	while (true) {
		if (_SwanQueue.empty()) {
			_Day++;
			for (auto& it : _IcePosV[_Day])
				_Map[it.first][it.second] = '.';
			for (auto& it : _IcePosV[0])
				_SwanQueue.push(it);
			_IcePosV[0].clear();
		}
		_Pos = _SwanQueue.front();
		_SwanQueue.pop();
		if (_Pos == _SwanPosV[1])
			break;
		for (int j = 0; j < 4; j++) {
			_dx = _Pos.first + _DxDy[j][0];
			_dy = _Pos.second + _DxDy[j][1];
			if (_dx >= _R || _dy >= _C || _dx < 0 || _dy < 0)
				continue;
			if (_isVisted[_dx][_dy]) 
				continue;
			if (_Map[_dx][_dy] == 'X') {
				_isVisted[_dx][_dy] = true;
				_IcePosV[0].push_back(make_pair(_dx, _dy));
				continue;
			}
			_SwanQueue.push(make_pair(_dx, _dy));
			_isVisted[_dx][_dy] = true;
		}
	}

	cout << _Day;
	return 0;
}

위와 같은 로직으로 진행하면 생각보다 메모리와 시간을 많이 소모한다.

한번의 BFS 탐색으로 문제를 해결하는 방법도 있지만 생각했던 방법으로 구현해보고 싶어서 진행