[C++] 백준 24390번: 또 전자레인지야?

문제 링크

24390번: 또 전자레인지야?

문제 요약

10초, 1분, 10분의 조리시간 버튼을 가진 전자레인지가 존재한다. 추가로 조리시작 버튼이 존재하는데, 조리시작 버튼은 현재 입력된 시간만큼 음식을 조리한다. 단, 조리시간이 0초이거나 이미 조리 중이라면 30초가 추가된다.
이 전자레인지로 주어진 시간을 조리하고자 할때, 버튼을 누르는 횟수의 최솟값을 구해야 한다.

접근 방법

제 경우에는 너비 우선 탐색으로 풀었지만, 다른 풀이도 존재할 것 같습니다. 시간들 사이에서 배수 관계가 성립하기 때문에 그리디 접근으로도 풀릴 것이라고 생각합니다.

너비 우선 탐색 풀이는 전형적인, 숨바꼭질 문제들과 동류로 보시면 될것 같습니다. 다만, 현재 조리 중인지 조리 중이 아닌지에 대한 판별을 위해 방문을 체크해주는 배열을 2차원으로 만들었습니다.

만약 조리 중이 아닌 상태에서 조리시작 버튼이 눌렸다면 시간은 추가하지 않아야 하고, 조리 상태를 반전시켜야 합니다. 만약 조리 중이면서 조리시작 버튼이 눌렸다면 시간만 30초 추가해야 합니다. 단, 0초에서 조리시작 버튼이 눌렸다면 시간을 30초 추가하면서도 조리 중으로 바뀌어야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int second, cnt;
	bool flag;
};

int button[4] = { 10, 60, 600, 30 };
bool visited[3601][2];

int main(void)
{
	string cooking_time;
	cin >> cooking_time;

	int m = stoi(cooking_time.substr(0, 2));
	int s = stoi(cooking_time.substr(3, 2));

	s += m * 60;

	queue<Data> q;
	q.push({ 0, 0, false });
	visited[0][0] = true;

	while (!q.empty())
	{
		auto now = q.front();
		q.pop();

		if (now.second == s && now.flag)
		{
			cout << now.cnt << '\n';
			return 0;
		}

		for (int i = 0; i < 4; i++)
		{
			Data next = { now.second + button[i], now.cnt + 1, now.flag };

			if (i == 3 && !now.flag)
			{
				next.flag = true;

				if(now.second)
					next.second -= button[i];
			}

			if (!visited[next.second][next.flag] && next.second <= s)
			{
				visited[next.second][next.flag] = true;
				q.push(next);
			}
		}
	}
}