[백준/BOJ] 백준 3197번 : 백조의 호수

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

3197번: 백조의 호수

이분 탐색, 파라메트릭 서치를 이용하여 특정한 날에 백조가 만날 수 있는지를 확인하여 백조가 만나는 가장 빠른 시간을 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

int r, c;
vector<string> board;
int board_day[1500][1500];
vector<pair<int, int>> water;
int discovered[1500][1500];
int depth[1500][1500];
vector<pair<int, int>> swan;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int lo = 0;
int hi = -1;

//백조가 day날 만날 수 있는지 확인
bool swanMeet(int day)
{
	memset(discovered, 0, sizeof(discovered));

	pair<int, int> start = swan[0]; //출발지점
	pair<int, int> dest = swan[1]; //목적지

	discovered[start.first][start.second] = 1;

	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//목적지에 도달 했을때
		if (here.first == dest.first && here.second == dest.second)
			return true;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			//day날 갈 수 있는 지점에만 갈 수 있다
			if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board_day[there.first][there.second] <= day && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}

	return false;
}

//이분 탐색을 통해 문제를 해결한다
int Solve()
{

	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;

		//mid날 백조가 만날 수 있는지 확인
		//만날 수 있다면 범위를 줄인다
		if (swanMeet(mid))
			hi = mid - 1;

		//만날 수 없다면 범위를 늘린다
		else
			lo = mid + 1;
	}

	return lo;
}

//입력받은 board로 몇일날 어느 곳을 갈 수 있는지 확인하기 위해 board_day를 만든다
void board_dayMake()
{
	memset(discovered, 0, sizeof(discovered));
	memset(depth, 0, sizeof(depth));

	queue<pair<int, int>> q;

	for (int i = 0; i < water.size(); i++)
	{
		q.push(water[i]);

		discovered[water[i].first][water[i].second] = 1;
		depth[water[i].first][water[i].second] = 0;
	}

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		board_day[here.first][here.second] = depth[here.first][here.second]; //depth날 이상일때 이 자리를 지날 수 있다고 표시 
		hi = max(hi, board_day[here.first][here.second]); //이분 탐색을 위해 가장 큰 수를 저장

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board[there.first][there.second] == 'X'&& discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;

				q.push(there);
			}
		}
	}
}

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

	string input;

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		cin >> input;
		board.push_back(input);

		for (int j = 0; j < c; j++)
		{
			if (board[i][j] == '.')
				water.push_back(make_pair(i, j));

			else if (board[i][j] == 'L')
			{
				board[i][j] = '.';

				swan.push_back(make_pair(i, j));
				water.push_back(make_pair(i, j));
			}
		}
	}

	board_dayMake();

	cout << Solve();

	return 0;
}