[백준 12869][C++] 뮤탈리스크 - 문제풀이

오늘 풀어볼 문제는 백준 12869의 뮤탈리스크 문제이다.

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

12869번: 뮤탈리스크

 

해당 문제는 가중치가 같은 최단 거리를 구하는 문제로 익숙한 2차원의 그래프가 아닌 다차원의 BFS로 생각하여 풀면 된다. 맨처음에는 DFS로도 풀어보려고 했지만 잘 풀리지 않았다...

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <stack>
#include <memory.h>

using namespace std;

const int INF = 987654321;

int dp[64][64][64], a[3], n, visited[64][64][64];

struct scvs {
	int a, b, c;
};

queue <scvs> q;


int _a[6][3] = {
	{9, 3, 1},
	{9, 1, 3},
	{3, 1, 9},
	{3, 9, 1},
	{1, 3, 9},
	{1, 9, 3}
};

int solve(int a, int b, int c)
{
	visited[a][b][c] = 1;
	q.push({ a,b,c });
	while (q.size())
	{
		int a = q.front().a;
		int b = q.front().b;
		int c = q.front().c;
		q.pop();
		if (visited[0][0][0]) break;
		for (int i = 0; i < 6; i++)
		{
			int na = max(0, a - _a[i][0]);
			int nb = max(0, b - _a[i][1]);
			int nc = max(0, c - _a[i][2]);
			if (visited[na][nb][nc] == 0)
			{
				visited[na][nb][nc] = visited[a][b][c] + 1;
				q.push({ na,nb,nc });
			}
		}
	}

	return visited[0][0][0];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	cout << solve(a[0], a[1], a[2]) - 1 << "\n";
	return 0;
}