이모티콘

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

14226번: 이모티콘

모든 연산은 1초가 걸린다! 시간의 최솟값 -> BFS

 

클립보드에 몇 개가 있는지에 따라서 만들 수 있는 다음 상태가 바뀐다!

정점을 나누어준다!

 

BFS를 할 때 굳이 check 배열을 안만들어도 판단이 가능하다!

memset(d, -1, sizeof(d));

0 이상이면 방문, -1이면 방문 x

 

s: screen c : clipboard

복사: (s,c) -> (s,s)

붙여넣기 : (s,c) -> (s+c, c)

삭제 : (s,c) -> (s-1, c)

 

클립보드에 있는 개수는 모르므로!!

ans를 구할 때 for문에 넣는다!

#include <iostream>
#include <queue>
#include <tuple>  //tie 함수
#include <cstring>
 
using namespace std;
 
int d[1001][1001];
 
int main()
{
    int n;
    cin >> n;
    memset(d, -1, sizeof(d));
    queue<pair<int, int>> q;
    //(s,c)
    q.push(make_pair(1, 0));
    d[1][0] = 0;
 
    while (!q.empty())
    {
        int s, c;
        s = q.front().first;
        c = q.front().second;
        //tie(s, c) = q.front();  // (s,c)를 묶어준다
        q.pop();
 
        //스크린을 클립보드에 복사
        if (d[s][s] == -1)
        {
            d[s][s] = d[s][c] + 1;
            q.push(make_pair(s, s));
        }
 
        //클립보드를 스크린에 복사
        if (s + c <= n && d[s + c][c] == -1)
        {
            d[s + c][c] = d[s][c] + 1;
            q.push(make_pair(s + c, c));
        }
 
        //스크린에서 하나 제거
        if (s - 1 >= 0 && d[s - 1][c] == -1)
        {
            d[s - 1][c] = d[s][c] + 1;
            q.push(make_pair(s - 1, c));
        }
    }
 
    int ans = -1;
    //screen에 n개 뜨는 것은 알지만 
    //그 때 클립보드의 개수는 모르므로 n번을 for문 해본다
    for (int i = 0; i <= n; i++)
    {
        if (d[n][i] != -1)
        {
            if (ans == -1 || ans > d[n][i])
            {
                ans = d[n][i]; //최소값이니까
            }
        }
    }
    cout << ans << '\n';
    return 0;
}