[C++] 백준(BOJ) - 12869 : 뮤탈리스크

25 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 12869 : 뮤탈리스크(링크)

알고리즘

1. 그래프 이론
2. 구조체
3. BFS

풀이

1. 가지가 셀수 있을 정도로 적은 경우 직접 배열로 만들어서 BFS 탐색 시 활용할 수 있다
2. 구조체를 직접 선언하여 tuple 형태와 흡사하게 자료형을 만들어서 사용할 수 있다
3. 값을 음수로 만들지 않기 위해 max함수를 활용할 수 있다

코드

// BOJ-12869 : 뮤탈리스크
#include<bits/stdc++.h>
using namespace std;

int n, a[3], visited[64][64][64];
int _a[6][3] = {
	{9,3,1},
	{9,1,3},
	{1,9,3},
	{1,3,9},
	{3,1,9},
	{3,9,1}
};

struct A { int a, b, c; };
queue<A> q;

int solve(int x, int y, int z)
{
	visited[x][y][z] = 1;
	q.push({ x,y,z });
	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]) continue;
			visited[na][nb][nc] = visited[a][b][c] + 1;
			q.push({ na,nb,nc });
		}
	}
	return visited[0][0][0] - 1;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	cout << solve(a[0], a[1], a[2]) << '\n';

	return 0;
}

평가

• 가중치가 같은 그래프 내에서 최단거리 탐색을 BFS를 활용하여 할 수 있다
• 입력을 배열을 통해 받으면 전역 변수로 선언한 배열 값은 0으로 초기화 되는 점을 이용할 수 있다