백준 12869번 뮤탈리스크 ( C++ )

문제

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

12869번: 뮤탈리스크

 

해설

3차원 길찾기 문제라고 생각하면 조금 더 쉬워지는 문제

중복되는 경우에 대한 예외처리는 꼭 해주자

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, scv[3], visited[62][62][62];
int ret;
 
void bfs(int a, int b, int c)
{
  queue<tuple<int, int, int>> q;
  visited[a][b][c] = 1;
  q.push({a, b, c});
  while (q.size())
  {
    tie(a, b, c) = q.front();
    q.pop();
    if (a == 0 && b == 0 && c == 0)
    {
      ret = visited[a][b][c] - 1;
      return;
    }
    if (!visited[max(a - 9, 0)][max(b - 3, 0)][max(c - 1, 0)])
    {
      q.push({max(a - 9, 0), max(b - 3, 0), max(c - 1, 0)});
      visited[max(a - 9, 0)][max(b - 3, 0)][max(c - 1, 0)] = visited[a][b][c] + 1;
    }
    if (!visited[max(a - 9, 0)][max(b - 1, 0)][max(c - 3, 0)])
    {
      q.push({max(a - 9, 0), max(b - 1, 0), max(c - 3, 0)});
      visited[max(a - 9, 0)][max(b - 1, 0)][max(c - 3, 0)] = visited[a][b][c] + 1;
    }
    if (!visited[max(a - 3, 0)][max(b - 9, 0)][max(c - 1, 0)])
    {
      q.push({max(a - 3, 0), max(b - 9, 0), max(c - 1, 0)});
      visited[max(a - 3, 0)][max(b - 9, 0)][max(c - 1, 0)] = visited[a][b][c] + 1;
    }
    if (!visited[max(a - 3, 0)][max(b - 1, 0)][max(c - 9, 0)])
    {
      q.push({max(a - 3, 0), max(b - 1, 0), max(c - 9, 0)});
      visited[max(a - 3, 0)][max(b - 1, 0)][max(c - 9, 0)] = visited[a][b][c] + 1;
    }
    if (!visited[max(a - 1, 0)][max(b - 9, 0)][max(c - 3, 0)])
    {
      q.push({max(a - 1, 0), max(b - 9, 0), max(c - 3, 0)});
      visited[max(a - 1, 0)][max(b - 9, 0)][max(c - 3, 0)] = visited[a][b][c] + 1;
    }
    if (!visited[max(a - 1, 0)][max(b - 3, 0)][max(c - 9, 0)])
    {
      q.push({max(a - 1, 0), max(b - 3, 0), max(c - 9, 0)});
      visited[max(a - 1, 0)][max(b - 3, 0)][max(c - 9, 0)] = visited[a][b][c] + 1;
    }
  }
}
 
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> scv[i];
  }
 
  bfs(scv[0], scv[1], scv[2]);
  cout << ret;
}