[백준/BOJ] 백준 6087번 : 레이저 통신

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

6087번: 레이저 통신

시작 위치에서 목적지로 가는데 필요한 거울 개수의 최솟값은 방향 전환의 최솟값이다. 위치 정보에 위치뿐만 아니라 이동하던 방향, 현재까지 사용한 거울의 수를 저장했다 그리고 discoverd에는 (x,y)위치에서 어떤 방향으로 이동 중일 때 사용한 거을 개수의 최솟값을 저장해서, 해당 위치를 단순히 발견했는지만 판단하지 말고, 발견을 했어도 해당 위치에 해당 방향으로 이동 중인데 거울의 사용 개수가 discoverd보다 더 작다면 탐색을 한다

 

코드

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


int w, h;
vector<string> board;
int discoverd[100][100][5]; //discoverd에는 (x,y)위치에서 어떤 방향으로 이동중일때 사용한 거을의 개수를 저장했다
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//discoverd에는 (x,y)위치에서 어떤 방향으로 이동중일때 사용한 거을의 개수를 저장을 해서, 해당위치를 단순히 발견했는지만 판단하지 말고, 발견을 했어도 해당위치에 해당방향으로 이동중인데 거울의 사용개수가 더 작다면 탐색을 한다
int Solve(pair<pair<int, int>, pair<int, int>> start, pair<int, int> dest)
{
	int ret = 987654321;

	//(x,y),(이동하던 방향,사용 거울의 수)를 저장하는 큐
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push(start);

	//start.second.first + 1을 하는 이유는 start.second.first의 값이 -1이라 한칸 뒤에 저장한다 (다른 방향들도 해당방향 숫자보다 한칸 뒤에 저장)(-1,0,1,2,3 -> 0,1,2,3,4)
	discoverd[start.first.first][start.first.second][start.second.first + 1] = start.second.second;

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

		q.pop();

		//현재까지 구한 거울의 수의 최소값이 here의 최솟값보다 작다면 here은 탐색의 의미가 없다
		if (ret < here.second.second)
			continue;

		//목적지에 도달한것중 거울의 사용수가 가장 작은 수를 구한다
		if (here.first.first == dest.first && here.first.second == dest.second)
		{
			ret = min(ret, here.second.second);
			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			if (here.second.first == i || here.second.first == -1) //같은 방향으로 가거나 초기 시작 위치에서 출발할때 (거울이 필요없다)
			{
				pair<pair<int, int>, pair<int, int>> there = make_pair(make_pair(here.first.first + dx_dy[i][0], here.first.second + dx_dy[i][1]), make_pair(i, here.second.second));

				if (there.first.first >= 0 && there.first.first < h && there.first.second >= 0 && there.first.second < w && board[there.first.first][there.first.second] != '*' && discoverd[there.first.first][there.first.second][there.second.first + 1] > there.second.second)
				{
					discoverd[there.first.first][there.first.second][there.second.first + 1] = there.second.second;
					q.push(there);
				}
			}
			else //다른방향으로 가면 거울 사용
			{
				pair<pair<int, int>, pair<int, int>> there = make_pair(make_pair(here.first.first + dx_dy[i][0], here.first.second + dx_dy[i][1]), make_pair(i, here.second.second + 1));

				if (there.first.first >= 0 && there.first.first < h && there.first.second >= 0 && there.first.second < w && board[there.first.first][there.first.second] != '*' && discoverd[there.first.first][there.first.second][there.second.first + 1] > there.second.second)
				{
					discoverd[there.first.first][there.first.second][there.second.first + 1] = there.second.second;
					q.push(there);
				}
			}
		}
	}

	return ret;
}

void Pre()
{
	//초기값을 매우 큰 수로 저장한다
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100; j++)
			for (int k = 0; k < 5; k++)
				discoverd[i][j][k] = 987654321;
}


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

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

	Pre();

	cin >> w >> h;

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

		for (int j = 0; j < w; j++)
		{
			if (board[i][j] == 'C')
			{
				//처음 발견한 'C'를 시작 위치로 하였다
				if (!have_start)
				{
					//start는 (x,y)위치와, (이동하던 방향(초기값은 -1), 사용한 거울의 개수)를 저장하였다
					start = make_pair(make_pair(i, j), make_pair(-1, 0));
					have_start = true;
				}

				//두번째 발견한 'C'는 목적지로 하였다
				else
					dest = make_pair(i, j);

				//시작지점과 목적지는 빈칸과 같이 '.'로 바꾸었다 (위치는 따로 저장 해놨으므로)
				board[i][j] = '.';
			}
		}
	}

	cout << Solve(start, dest);

	return 0;
}