[G4] 백준 12869번 뮤탈리스크 C++ 너비 우선 탐색, 우선순위 큐

리뷰

 

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

뮤탈리스크의 쓰리쿠션으로 SCV를 최소한의 공격으로 모두 잡는 문제

 

 

전역 변수

• n : SCV의 개수를 저장할 변수
• v : SCV의 체력을 인덱스로 사용해 방문 여부를 체크할 논리형 3차 배열
• SCV : SCV의 체력과 소요한 시간을 정의할 구조체, 소요 시간을 기준으로 오름차순 정렬한다.

 

함수

1. ATK

SCV ATK(int s1, int s2, int s3, int t)

 

뮤탈리스크의 공격을 구현하기 위한 함수

1. 매개변수로 scv들의 체력 s1, s2, s3와 현재 까지 소요 시간 t를 전달받는다.
2. s1에 9를 빼주고, 값이 0보다 작을 경우 0으로 초기화 해준다.
3. s2에 3을 빼주고, 값이 0보다 작을 경우 0으로 초기화 해준다.
4. s3에 1을 빼주고, 값이 0보다 작을 경우 0으로 초기화 해준다.
5. s1, s2, s3와 소요시간을 1만큼 증가시켜 묶은 뒤 SCV타입의 변수로 리턴한다.

---

2. bfs

int bfs(SCV& scv)

 

너비 우선 탐색을 통해 SCV를 최단 시간 내에 잡는 케이스를 출력하는 함수

1. 매개변수로 scv의 초기값을 전달받는다.
2. SCV타입의 우선순위 큐 q를 초기화 한다.
3. q에 초기 scv정보를 push해주고, 해당 scv의 체력을 방문처리 해준다.
4. q가 빌 때 까지 while루프를 수행한다, 매 루프마다 요소를 한개씩 뽑아내 준다.
5. 기저 조건으로 만약 모든 scv의 체력이 0이라면 소요 시간을 리턴해 준다.
6. 6개의 경우의 수에 대해 공격을 진행하고, 방문처리 되지 않았다면 방문처리 후 q에 삽입해 준다.
7. 기저 조건에 도달할 때 까지 위 로직을 반복 수행해 준다.

 

문제풀이

1. n값을 입력 받고, scv의 초기값을 모두 0인 상태로 초기화 해준다.
2. n번의 반복문을 수행하고, 각 scv의 초기 hp를 입력 받아 저장해 준다.
3. bfs함수에 scv를 매개변수로 전달하여 호출 후 리턴값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

경우의 수가 6개밖에 되지 않기 때문에 각 케이스를 하드코딩 해주었다.

 

 

정답 코드

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

int n;
bool v[61][61][61];
struct SCV {
	int s1, s2, s3, t;
	bool operator < (const SCV& other) const {
		return t > other.t;
	}
};

SCV ATK(int s1, int s2, int s3, int t) {
	s1 = s1 - 9 >= 0 ? s1 - 9 : 0;
	s2 = s2 - 3 >= 0 ? s2 - 3 : 0;
	s3 = s3 - 1 >= 0 ? s3 - 1 : 0;
	return { s1, s2, s3, t + 1 };
}

int bfs(SCV& scv) {
	priority_queue<SCV> q;
	q.push(scv);
	v[scv.s1][scv.s2][scv.s3] = 1;

	while (!q.empty()) {
		SCV scv = q.top(); q.pop();
		int s1 = scv.s1, s2 = scv.s2, s3 = scv.s3, ct = scv.t;
		if (!s1 && !s2 && !s3) return ct;

		scv = ATK(s1, s2, s3, ct);
		if (!v[scv.s1][scv.s2][scv.s3]) {
			v[scv.s1][scv.s2][scv.s3] = 1;
			q.push({ scv.s1, scv.s2, scv.s3, scv.t });
		}

		scv = ATK(s1, s3, s2, ct);
		if (!v[scv.s1][scv.s3][scv.s2]) {
			v[scv.s1][scv.s3][scv.s2] = 1;
			q.push({ scv.s1, scv.s3, scv.s2, scv.t });
		}

		scv = ATK(s2, s1, s3, ct);
		if (!v[scv.s2][scv.s1][scv.s3]) {
			v[scv.s2][scv.s1][scv.s3] = 1;
			q.push({ scv.s2, scv.s1, scv.s3, scv.t });
		}

		scv = ATK(s2, s3, s1, ct);
		if (!v[scv.s2][scv.s3][scv.s1]) {
			v[scv.s2][scv.s3][scv.s1] = 1;
			q.push({ scv.s2, scv.s3, scv.s1, scv.t });
		}

		scv = ATK(s3, s1, s2, ct);
		if (!v[scv.s3][scv.s1][scv.s2]) {
			v[scv.s3][scv.s1][scv.s2] = 1;
			q.push({ scv.s3, scv.s1, scv.s2, scv.t });
		}

		scv = ATK(s3, s2, s1, ct);
		if (!v[scv.s3][scv.s2][scv.s1]) {
			v[scv.s3][scv.s2][scv.s1] = 1;
			q.push({ scv.s3, scv.s2, scv.s1, scv.t });
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	SCV scv = { 0, 0, 0, 0 };
	for (int i = 0; i < n; ++i) {
		int hp; cin >> hp;
		if (i == 0) scv.s1 = hp;
		else if (i == 1) scv.s2 = hp;
		else scv.s3 = hp;
	}

	cout << bfs(scv);
}