[백준/BOJ] 백준 2151번 : 거울 설치

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

2151번: 거울 설치

같은 지점이라도 이 지점에서 어떤 방향으로 직진하는지에 따른 정보를 저장했다. there지점을 확인할 때는 범위를 벗어나지 않고, 벽이 아니고, there 지점에서의 거울 사용 횟수보다 here 지점의 거울 사용 횟수가 작을 때 확인했다. 그리고 거울을 설치할 경우 현재 방향에서 거울에 의해 바뀌는 방향의 정보도 저장했다

 

코드

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

int n;
vector<string> board;
int mirror_cnt[50][50][4];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int Solve(pair<int, int> start, pair<int, int> dest)
{
	int ret = 987654321;

	queue<pair<pair<int, int>, int>> q;

	//해당 지점에서 어떤 방향으로 직진하는지(0~4)도 저장해 놓는다
	for (int i = 0; i < 4; i++)
	{
		mirror_cnt[start.first][start.second][i] = 0;
		q.push(make_pair(start, i));
	}

	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, mirror_cnt[here.first.first][here.first.second][here.second]);

		for (int i = 0; i < 4; i++)
		{
			//직진할 수 있는 방향이 아닐때
			if (here.second != i)
				continue;

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

			//범위를 벗어나지 않고 벽이 아니고 there 지점에서의 거울 사용 횟수보다 here 지점의 거울 사용 횟수가 작을때
			if (there.first.first >= 0 && there.first.first < n && there.first.second >= 0 && there.first.second < n && board[there.first.first][there.first.second] != '*' && mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second])
			{
				//there지점에 거울을 설치 하지 않을 경우(거울 사용이 증가하지 않는다) (거울 설치 가능지점과 가능하지 않은 지점 모두 해당)
				mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second];
				q.push(there);
				
				//거울 설치 가능한 지점에 거울을 설치할 경우
				if (board[there.first.first][there.first.second] == '!')
				{
					//현재 직진방향에 따라 반사되는 방향이 있다
					if (i == 0)
					{
						there.second = 1;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}

						there.second = 3;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}
					}
					else if (i == 1)
					{
						there.second = 0;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}

						there.second = 2;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}
					}
					else if (i == 2)
					{
						there.second = 1;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}

						there.second = 3;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}
					}
					else if (i == 3)
					{
						there.second = 0;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}

						there.second = 2;
						if (mirror_cnt[there.first.first][there.first.second][there.second] > mirror_cnt[here.first.first][here.first.second][here.second] + 1)
						{
							mirror_cnt[there.first.first][there.first.second][there.second] = mirror_cnt[here.first.first][here.first.second][here.second] + 1;
							q.push(there);
						}
					}
				}
			}
		}
	}

	return ret;
}

void Pre()
{
	for (int i = 0; i < 50; i++)
		for (int j = 0; j < 50; j++)
			for (int k = 0; k < 4; k++)
				mirror_cnt[i][j][k] = 987654321;
}

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

	string temp;
	pair<int, int> start;
	pair<int, int> dest;
	bool start_check = false;

	Pre();

	cin >> n;

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

		for (int j = 0; j < n; j++)
		{
			if (temp[j] == '#')
			{
				if (!start_check)
				{
					start = make_pair(i, j);
					start_check = true;
				}

				else
				{
					dest = make_pair(i, j);
				}
			}
		}
		board.push_back(temp);
	}

	cout << Solve(start, dest);

	return 0;
}