[백준/BOJ] 백준 16137번 : 견우와 직녀

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

16137번: 견우와 직녀

다리를 건널 때는 주기에 맞을 때 건너는 것(기다렸다가 건너는 것)을 처리해야 한다

 

코드

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

int n, m;
int board[10][10];
int depth[10][10][2]; //[2]는 현재 땅인지 다리위 인지를 표시하기 위해서 이다.
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
vector<pair<int, int>> cliff;

void Pre()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			for (int k = 0; k < 2; k++)
				depth[i][j][k] = 987654321;
}

int Find(pair<int, int> start, pair<int, int> dest)
{
	Pre();

	int ret = 987654321;
	queue<pair<pair<int, int>, int>> q;

	//시작위치가 땅일때
	if (board[start.first][start.second] == 1)
	{
		depth[start.first][start.second][0] = 0;
		q.push(make_pair(start, 0));
	}

	//시작위치가 다리일때
	else
	{
		depth[start.first][start.second][1] = 0;
		q.push(make_pair(start, 1));
	}

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

		//목적지에 도착 했을때
		if (here.first.first == dest.first && here.first.second == dest.second)
			ret = min(ret, depth[here.first.first][here.first.second][here.second]);

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

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] != 0)
			{
				//땅을 걸을때
				if (board[there.first][there.second] == 1)
				{
					if (depth[there.first][there.second][0] > depth[here.first.first][here.first.second][here.second] + 1)
					{
						depth[there.first][there.second][0] = depth[here.first.first][here.first.second][here.second] + 1;
						q.push(make_pair(there, 0));
					}
				}

				//다리를 걸을때(다리를 두번연속 지날 수 없으므로 here.second == 0 일때만 다리 걷기 가능)
				if (board[there.first][there.second] >= 2 && here.second == 0)
				{
					//다리의 주기에 맞을때 건넌다(기다린다)
					int temp = depth[here.first.first][here.first.second][here.second] % board[there.first][there.second];
					temp = board[there.first][there.second] - temp;
					temp = depth[here.first.first][here.first.second][here.second] + temp;

					if (depth[there.first][there.second][1] > temp)
					{
						depth[there.first][there.second][1] = temp;
						q.push(make_pair(there, 1));
					}
				}
			}
		}
	}

	return ret;
}

//here_cliff절벽 위치에 다리를 설치할 수 있는지 확인
bool bridgeCan(pair<int, int> here_cliff)
{
	vector<int> check(4, 0);

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

		if (there_cliff.first >= 0 && there_cliff.first < n && there_cliff.second >= 0 && there_cliff.second < n && board[there_cliff.first][there_cliff.second] == 0)
			check[i] = 1;
	}

	if (check[0] == 1)
	{
		if (check[1] == 1 || check[3] == 1)
			return false;
	}

	else if (check[1] == 1)
	{
		if (check[0] == 1 || check[2] == 1)
			return false;
	}

	else if (check[2] == 1)
	{
		if (check[1] == 1 || check[3] == 1)
			return false;
	}

	else if (check[3] == 1)
	{
		if (check[2] == 1 || check[0] == 1)
			return false;
	}

	return true;
}

int Solve()
{
	int ret = 987654321;

	for (int i = 0; i < cliff.size(); i++)
	{
		//다리를 설치할 수 있는 절벽일때
		if (bridgeCan(cliff[i]))
		{
			board[cliff[i].first][cliff[i].second] = m; //다리를 설치해본다
			ret = min(ret, Find(make_pair(0, 0), make_pair(n - 1, n - 1)));
			board[cliff[i].first][cliff[i].second] = 0; //다리 설치 해제
		}
	}

	return ret;
}

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

	int input;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> input;
			board[i][j] = input;

			//절벽의 위치를 저장한다
			if (input == 0)
				cliff.push_back(make_pair(i, j));
		}

	cout << Solve();

	return 0;
}