[백준/BOJ] 백준 1726번 : 로봇

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

1726번: 로봇

해당 위치에서 어떤 방향으로 있는지를 확인해 그때 할 수 있는 명령(이동 또는 방향 전환)을 통해 도착지점에 원하는 방향으로 가는데 필요한 명령 횟수의 최솟값을 구한다

 

코드

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

int m, n;
int board[100][100];
int discovered[100][100][4];
int depth[100][100][4];

//동, 서, 남, 북
int dx_dy1[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int dx_dy2[4][2] = { {0,2},{0,-2},{2,0},{-2,0} };
int dx_dy3[4][2] = { {0,3}, {0,-3}, {3,0}, {-3,0} };

int Solve(pair<pair<int, int>, int> start, pair<pair<int, int>, int> dest)
{
	discovered[start.first.first][start.first.second][start.second] = 1;
	depth[start.first.first][start.first.second][start.second] = 0;

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

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

		//도착위치에 원하는 방향으로 도착했을때
		if (here.first.first == dest.first.first && here.first.second == dest.first.second && here.second == dest.second)
			return depth[here.first.first][here.first.second][here.second];

		for (int i = 0; i < 4; i++) //동,서,남,북으로 방향전환
		{
			if (here.second == i) //같은 방향이라면 1~3칸 갈 수 있다
			{
				pair<pair<int, int>, int> there;

				//1칸이동
				there = make_pair(make_pair(here.first.first + dx_dy1[i][0], here.first.second + dx_dy1[i][1]), i);
				if (there.first.first >= 0 && there.first.first < m && there.first.second >= 0 && there.first.second < n && board[there.first.first][there.first.second] == 0 && discovered[there.first.first][there.first.second][there.second] == 0)
				{
					discovered[there.first.first][there.first.second][there.second] = 1;
					depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;

					q.push(there);
				}

				//2칸이동
				there = make_pair(make_pair(here.first.first + dx_dy2[i][0], here.first.second + dx_dy2[i][1]), i);
				if (there.first.first >= 0 && there.first.first < m && there.first.second >= 0 && there.first.second < n && board[there.first.first][there.first.second] == 0 && board[here.first.first + dx_dy1[i][0]][here.first.second + dx_dy1[i][1]] == 0 && discovered[there.first.first][there.first.second][there.second] == 0)
				{
					discovered[there.first.first][there.first.second][there.second] = 1;
					depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;

					q.push(there);
				}
				//3칸이동
				there = make_pair(make_pair(here.first.first + dx_dy3[i][0], here.first.second + dx_dy3[i][1]), i);
				if (there.first.first >= 0 && there.first.first < m && there.first.second >= 0 && there.first.second < n && board[there.first.first][there.first.second] == 0 && board[here.first.first + dx_dy1[i][0]][here.first.second + dx_dy1[i][1]] == 0 && board[here.first.first + dx_dy2[i][0]][here.first.second + dx_dy2[i][1]] == 0 && discovered[there.first.first][there.first.second][there.second] == 0)
				{
					discovered[there.first.first][there.first.second][there.second] = 1;
					depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;

					q.push(there);
				}
			}

			else //방향 전환만 할때
			{
				pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first, here.first.second), i);

				if (discovered[there.first.first][there.first.second][there.second] == 0)
				{
					//180도 방향전환은 한번에 할 수 없다
					if ((here.second == 0 && there.second == 1) || (here.second == 1 && there.second == 0) || (here.second == 2 && there.second == 3) || (here.second == 3 && there.second == 2))
						continue;

					else
					{
						discovered[there.first.first][there.first.second][i] = 1;
						depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;
						
						q.push(there);
					}
				}
			}
		}

	}

	return -1;
}

void Pre()
{
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100; j++)
			for (int k = 0; k < 4; k++)
				discovered[i][j][k] = 0;
}

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

	int temp;
	pair<pair<int, int>, int> start;
	pair<pair<int, int>, int> dest;
	int x, y, d;

	Pre();

	cin >> m >> n;

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

	//왼쪽 상단을 (0,0)으로 쓰기 위해 x-1,y-1,을 하였고 방향도 0부터 시작하기 위해 d-1을 하였다
	cin >> x >> y >> d;
	start = make_pair(make_pair(x - 1, y - 1), d - 1);

	cin >> x >> y >> d;
	dest = make_pair(make_pair(x - 1, y - 1), d - 1);

	cout << Solve(start, dest);

	return 0;
}