[G5] 백준 19940번 피자 오븐 C++ 너비 우선 탐색

리뷰

 

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

BFS로 0 ~ 59초에 해당하는 모든 그리디한 값을 구해두고 O(1)로 푸는 문제

 

 

전역 변수

• N : 시뮬레이션 시 나올 수 있는 최대값을 저장할 상수 변수
• t : 테스트 케이스의 개수를 저장할 변수
• n : 테스트 케이스 마다 시간을 저장할 변수
• T : 각 버튼을 클릭한 횟수 ah, at, mt, ao, mo와 남은 시간 cur을 정의할 구조체
• ts : 각 버튼을 클릭한 횟수의 최적값을 저장할 T타입 배열
• v : 시간 방문 여부를 체크하기 위한 배열

 

함수

1. bfs

void bfs()

 

너비 우선 탐색을 통해 각 시간에 도달하는 최적값을 구하기 위한 함수

1. T타입의 큐 q를 초기화 하고, 모든 값을 0인 상태로 q에 push해준다.
2. q가 빌 때 까지 while 루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
3. 시간값이 0에서 60사이 이면서 현재 시간에 방문처리가 되어있지 않을 경우 로직을 수행한다.
4. 현재 시간에 방문처리 후 ts배열에 현재 클릭한 정보 값을 저장해 준다.
5. 이후 모든 경우에 대해 q에 푸시해 준다. 이 때 우선순위에 따라 q에 push하는 순서가 달라야 한다.

 

문제풀이

1. bfs함수를 실행하여 0 ~ 59초에 해당하는 최적값을 구해 ts배열에 저장해 준다.
2. t를 입력 받고, t번의 while문을 수행하여 매 루프마다 n값을 입력 받아준다.
3. 변수 div에 n을 60으로 나눈 몫을 저장하고, n을 60으로 나눈 나머지를 저장한다.
4. ts배열의 n번째 인덱스에 저장된 값들을 출력해 준다.

 

트러블 슈팅

1. 우선순위 큐를 사용해 매번 bfs를 돌려 최적화 작업을 시도했다가 반례에서 막혔다.
2. 어차피 가중치가 없으므로 미리 값을 구해두는 방식을 사용했으나 fail을 받았다.
3. 0~59초 케이스를 돌려보니 30~50초때에 이상한 점이 발견되었다.
4. 마찬가지로 가중치가 없으므로 q에 push하는 순서가 우선순위와 연관성이 있는 것을 찾아 고치니 AC를 받았다.

 

참고 사항

• q에 push할 때는 우선순위가 높은 순서대로 push를 진행해 주어야 한다.

 

정답 코드

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

const int N = 61;
int t, n;
struct T {
	int ah, at, mt, ao, mo, cur;
};
T ts[N];
bool v[N];

void bfs() {
	queue<T> q;
	q.push({ 0, 0, 0, 0, 0, 0 });

	while (!q.empty()) {
		T t = q.front(); q.pop();
		int ah = t.ah, at = t.at, mt = t.mt, ao = t.ao, mo = t.mo, cur = t.cur;

		if (0 <= cur && cur <= 60 && !v[cur]) {
			v[cur] = true;
			ts[cur] = t;
			q.push({ ah, at, mt, ao, mo + 1, cur - 1 });
			q.push({ ah, at, mt, ao + 1, mo, cur + 1 });
			q.push({ ah, at, mt + 1, ao, mo, cur - 10 });
			q.push({ ah, at + 1, mt, ao, mo, cur + 10 });
			q.push({ ah + 1, at, mt, ao, mo, cur + 60 });
		}
	}
}

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

	bfs();
	cin >> t;
	while (t--) {
		cin >> n;
		int div = n / 60;
		n %= 60;
		cout << ts[n].ah + div << " " << ts[n].at << " " << ts[n].mt << " " << ts[n].ao << " " << ts[n].mo << "\n";
	}
}