[BOJ/백준 3197/C++] 백조의 호수

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

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초

- 메모리 제한 : 256MB

 

[문제 풀이]

이번 문제는 이전에 풀었던 치즈 문제와 유사해 보인다.

https://tobrother.tistory.com/11

[BOJ/백준 2638/C++] 치즈

 

하지만 치즈 문제처럼 하루마다 빙판을 녹이고 두 백조가 만날 수 있는지 탐색하는 방법을 사용하면 아마도 시간초과가 걸릴 것이다.

 

왜냐하면 주어지는 호수의 크기가 최대 1500x1500이고 100일만 되어도 2억번이 넘는 연산을 수행하게 된다. 따라서 최대한 탐색횟수를 줄이면서 백조들이 언제 만날 수 있는지 계산을 해야된다.

 

먼저 생각해 볼 수 있는 점은 "굳이 하루마다 빙판을 녹이는 탐색을 해야하는가?" 이 점이다.

 

빙판을 녹이는 탐색이 연산의 절반 정도는 잡아먹기 때문에 이 부분을 줄일 필요가 있다.

 

그렇다면 생각해볼 수 있는 방법은 BFS 탐색 한번으로 모든 빙판에 대하여 그 빙판이 언제 녹는지 구할 수 있다.

문제에서 주어진 예제 2번을 한번 나타내보면 다음과 같다.

물 지역은 0으로 초기화하고 X지점을 탐색할때마다 (현재지점 + 1)값을 다음 이동할 곳에 저장하면서 BFS를 수행하면 오른쪽 표와 같이 각 빙판이 언제 녹는지 구할 수 있다.

 

다음으로는 두개의 L지점 중 하나에서 탐색을 시작하여 또 다른 L지점까지 탐색을 진행하는데 방법은 다음과 같이 진행한다.

• 우선순위 큐를 이용하여 탐색을 진행한다. 원소는 pair<int,pair<int,int>> 
  • 첫번째 int는 pair<int,int> 지점의 빙판이 녹는 날을 의미한다. 예를들어 2면 이틀 뒤에 녹는다는 것을 의미함
  • 두번째 요소인 pair<int,int>는 방판의 좌표를 나타낸다.
  • 우선순위 큐의 정렬 조건은 첫번째 int를 기준으로 오름차순으로 정렬한다. (최대한 녹는날이 빠른 지점부터 확인)
• 탐색을 진행하면서 정답을 의미하는 변수 ans를 우선순위 큐의 첫번째 원소의 최대값으로 갱신한다. 
• 두번째 L의 위치에 도착하면 탐색을 종료하고 정답 ans를 출력한다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define mod 10007
#define pii pair<int,int>

using namespace std;

int R, C;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<vector<char>> omp;
vector<vector<int>> dmp;
vector<pii> duck;

struct cmp
{
	bool operator()(pair<int, pii>& a, pair<int, pii>& b)
	{
		return a.first > b.first;
	}
};

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

	cin >> R >> C;

	omp.resize(R); for (int i = 0; i < R; i++) omp[i].resize(C);
	dmp.resize(R); for (int i = 0; i < R; i++) dmp[i].resize(C);
	
	queue<pii> q;
	vector<vector<bool>> ck(R, vector<bool>(C, 0));
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> omp[i][j];
			if (omp[i][j] == '.') { q.push({ i,j }); ck[i][j] = true; }
			else if (omp[i][j] == 'L') { q.push({ i,j }); ck[i][j] = true; duck.push_back({ i,j }); }
		}
	}
	
	while (!q.empty())
	{
		pii tmp = q.front(); q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = tmp.second + dx[i];
			int ny = tmp.first + dy[i];

			if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;
			if (ck[ny][nx]) continue;

			ck[ny][nx] = true;
			if (omp[ny][nx] == 'X') dmp[ny][nx] = dmp[tmp.first][tmp.second] + 1;
			q.push({ ny,nx });
		}
	}

	priority_queue<pair<int, pii>, vector<pair<int,pii>>, cmp> pq;
	pq.push({ 0,{duck[0].first, duck[0].second} });
	for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) ck[i][j] = false;
	ck[duck[0].first][duck[0].second] = true;
	int ans = 0;
	while (!pq.empty())
	{
		pair<int, pii> tmp = pq.top(); pq.pop();
		ans = max(ans, tmp.first);
		if (tmp.second.first == duck[1].first & tmp.second.second == duck[1].second) break;
		
		for (int i = 0; i < 4; i++)
		{
			int nx = tmp.second.second + dx[i];
			int ny = tmp.second.first + dy[i];
			
			if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;
			if (ck[ny][nx]) continue;
			ck[ny][nx] = true;
			pq.push({ dmp[ny][nx], {ny,nx} });
		}
	}
	cout << ans;
}

이번 문제는 발상의 전환이 필요했던 문제였다. BFS를 단순히 방문했다 or 안했다 의 기준으로 탐색하는 것이 아니라 그 지점이 언제 녹는지에 대한 관점으로 바꾸면 쉽게 풀리는 문제였다.

 

굳