백준 문제 24390번 또 전자레인지야? 문제풀이 c++

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

24390번: 또 전자레인지야?

 

문제해석

 

이 문제를 처음 봤을때 제일 먼저 떠오른게 너비우선탐색이여서 그렇게 작성했다.

그런데 풀고나서 문제 태그를 보았는데 그리디알고리즘이 있는데 11047번 동전 0 문제와 동일한 아이디어로 해결이 가능한것을 알아챘다.

여기선 처음 풀었던 방법인 그래프 탐색 코드를 넣었다.

 

먼저 입력된 시간을 분시간으로 단위를 변환 해준 후 버튼이 10분 60분 600분 30분짜리 4개가 있다고 생각하고

눌러준 시간에 도달했다면 ans값을 작은 값으로 갱신해주는 방식으로 하였다.

또 30분짜리 버튼을 눌렀는가?를 판단하는 flag를 두어서 아직 누르지않았다면 그 버튼을 눌러야하므로 카운트를 1 더해주고 눌렀다면 더하지 않았다.

 

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <tuple>
using namespace std;
void bfs();
int a[4]={10,60,600,30};
queue < tuple<int,bool,int> > q; //flag 0 조리 시작안함 1 조리중
bool visited[3601];
int time_min;
int ans=99999999;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    string s;
    cin>>s;
    time_min=((int)s[0]-(int)'0')*600+((int)s[1]-(int)'0')*60+((int)s[3]-(int)'0')*10+((int)s[4]-(int)'0');
    q.push({0,0,0});
    bfs();
    cout<<ans;
}
void bfs(){
    while(!q.empty())
    {
        int cur=get<0>(q.front());
        bool flag=get<1>(q.front());
        int cnt=get<2>(q.front());
        q.pop();
        if(cur==time_min)
        {
            if(flag==0)
            {
                ans=min(ans,cnt+1);
            }
            else
            {
                ans=min(ans,cnt);
            }
        }
        for(int i=0; i<4; i++)
        {
            int next=cur+a[i];
            if(i==3)
            {
                if((0<=next&&next<3601)&&visited[next]==0)
                {  
                    visited[next]=1;
                    q.push({next,1,cnt+1});
                }
            }
            else
            {
                if((0<=next&&next<3601)&&visited[next]==0)
                {  
                    visited[next]=1;
                    if(flag==0)
                    {
                        q.push({next,0,cnt+1});
                    }
                    else
                    {
                        q.push({next,1,cnt+1});
                    }
                }
            }
        }
    }
}