[백준/BOJ] 백준 20549번 : 인덕이의 고민

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

20549번: 인덕이의 고민

[먹은 음식 상황][행][열] = 최소비용을 저장하여 다익스트라를 구현해 문제를 해결했다

 

코드

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

int n;
int a, b, c;
int m;
vector<vector<int>> board(50, vector<int>(50, -1));
int a_dxdy[8][2] = { {-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2} };
int b_dxdy[4][2] = { {-1,-1},{-1,1},{1,1},{1,-1} };
int c_dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int Solve(pair<int, int> start)
{
	int result[1 << 4][50][50]; //[먹은 음식 상황][행][열]
	priority_queue <tuple<int, int, pair<int, int>>> pq; //[-비용][먹은 음식 상황][(위치)]

	for (int i = 0; i < (1 << 4); i++)
		for (int j = 0; j < 50; j++)
			for (int k = 0; k < 50; k++)
				result[i][j][k] = 987654321;

	result[0][start.first][start.second] = 0;
	pq.push(make_tuple(-0, 0, start));

	while (!pq.empty())
	{
		pair<int, int> here = get<2>(pq.top());
		int here_eat = get<1>(pq.top());
		int here_cost = -get<0>(pq.top());
		pq.pop();

		if (result[here_eat][here.first][here.second] < here_cost)
			continue;

		if (here_eat == ((1 << m) - 1))
			return here_cost;

		//a(나이트) 방향으로 갈때
		for (int i = 0; i < 8; i++)
		{
			pair<int, int> there = make_pair(here.first + a_dxdy[i][0], here.second + a_dxdy[i][1]);
			int there_cost = here_cost + a;
			int there_eat = here_eat;

			//there가 범위 안에 있을때
			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n)
			{
				//there위치가 먹이 위치일때
				if (board[there.first][there.second] != -1)
				{
					there_eat |= (1 << board[there.first][there.second]);
				}

				if (result[there_eat][there.first][there.second] > there_cost)
				{
					result[there_eat][there.first][there.second] = there_cost;

					pq.push(make_tuple(-there_cost, there_eat, there));
				}
			}
		}

		//b(비숍) 방향으로 갈때
		for (int i = 0; i < 4; i++)
		{
			int cnt = 1;
			while (1)
			{
				pair<int, int> there = make_pair(here.first + (b_dxdy[i][0] * cnt), here.second + (b_dxdy[i][1] * cnt));
				int there_cost = here_cost + b;
				int there_eat = here_eat;

				//there가 범위 안에 있을때
				if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n)
				{
					//there위치가 먹이 위치일때
					if (board[there.first][there.second] != -1)
					{
						there_eat |= (1 << board[there.first][there.second]);
					}

					if (result[there_eat][there.first][there.second] > there_cost)
					{
						result[there_eat][there.first][there.second] = there_cost;

						pq.push(make_tuple(-there_cost, there_eat, there));
					}

					cnt++;
				}

				else
					break;
			}
		}

		//c(룩) 방향으로 갈때
		for (int i = 0; i < 4; i++)
		{
			int cnt = 1;
			while (1)
			{
				pair<int, int> there = make_pair(here.first + (c_dxdy[i][0] * cnt), here.second + (c_dxdy[i][1] * cnt));
				int there_cost = here_cost + c;
				int there_eat = here_eat;

				//there가 범위 안에 있을때
				if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n)
				{
					//there위치가 먹이 위치일때
					if (board[there.first][there.second] != -1)
					{
						there_eat |= (1 << board[there.first][there.second]);
					}

					if (result[there_eat][there.first][there.second] > there_cost)
					{
						result[there_eat][there.first][there.second] = there_cost;

						pq.push(make_tuple(-there_cost, there_eat, there));
					}

					cnt++;
				}

				else
					break;
			}
		}
	}
}

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

	cin >> n;

	cin >> a >> b >> c;

	pair<int, int> start;
	int x, y;

	cin >> x >> y;
	start = make_pair(x, y);

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int xi, yi;
		cin >> xi >> yi;

		board[xi][yi] = i;
	}

	cout << Solve(start);

	return 0;
}