[백준/BOJ] 백준 18128번 : 치삼이의 징검다리 건너기

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

18128번: 치삼이의 징검다리 건너기

각 위치에 물이 며칠에 차오르는지 표시하고, 이분 탐색을 이용해 도착점에 도달할 수 있는 가장 빠른 날짜를 계산하여 문제를 해결했다.

 

코드

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

int n, w;
vector<pair<int, int>> water;
vector<string> board;
int water_depth[1000][1000];
int water_depth_max = -1;
int dxdy[8][2] = { {0,-1},{-1,0},{0,1},{1,0}, {-1,-1},{-1,1},{1,1},{1,-1} }; //[4~][]부터는 대각선 방향

//water_depth에 각 위치에 물이 몇일에 차오르는지 저장한다
void WaterDepth()
{
	for (int i = 0; i < 1000; i++)
		for (int j = 0; j < 1000; j++)
			water_depth[i][j] = -1;

	queue<pair<int, int>> q;
	for (int i = 0; i < water.size(); i++)
	{
		water_depth[water[i].first][water[i].second] = 0;
		q.push(water[i]);
	}

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

		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 < n && there.second >= 0 && there.second < n && water_depth[there.first][there.second] == -1)
			{
				water_depth[there.first][there.second] = water_depth[here.first][here.second] + 1;
				q.push(there);
			}

		}
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			water_depth_max = max(water_depth_max, water_depth[i][j]);
}

//day일날 도착점에 도달할 수 있는지 확인
bool Check(int day)
{
	vector<vector<int>> discovered(1000, vector<int>(1000, 0));
	queue<pair<int, int>> q;

	discovered[0][0] = 1;
	q.push(make_pair(0, 0));

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

		//도착지점에 도착했을때
		if (here.first == n - 1 && here.second == n - 1)
			return true;

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

			//이동하는곳이 범위를 넘어가지 않고, 발견되지 않은곳이고, 돌이고, 물이 차오르고 나서 날짜이거나 도착지점일때
			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && discovered[there.first][there.second] == 0 && board[there.first][there.second] == '1' && ((water_depth[there.first][there.second] <= day) || (there.first == n - 1 && there.second == n - 1)))
			{
				discovered[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}

	return false;
}

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

	cin >> n >> w;

	for (int i = 0; i < w; i++)
	{
		int x, y;
		cin >> x >> y;
		water.push_back(make_pair(x - 1, y - 1));
	}
	WaterDepth();

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	//이분 탐색으로 몇일에 도착지점에 도달할 수 있는지 확인
	int left = 0;
	int right = water_depth_max; //물이 다 퍼질때 최대 날짜
	int result = -1;
	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (Check(mid) == true)
		{
			result = mid;

			right = mid - 1;
		}

		else
			left = mid + 1;
	}

	cout << result;

	return 0;
}