[BOJ] 이모티콘(14226)

[백준(BOJ)] 이모티콘(14226) C++

문제 : BOJ_14226번 이모티콘

문제 설명

bfs

처음에 한 개의 이모티콘이 있고

이모티콘을 클립보드에 저장할 때 count +1

이모티콘을 붙여넣기 할 때 count +1(클립보드가 비어있으면 안 됩니다.)

현재 이모티콘의 수를 -1 할 때 count +1

일 때 주어지는 수의 이모티콘 개수가 될 때까지 최소 count를 구하는 문제입니다.

---

Solution

최솟값을 구해야 되기 때문에 bfs를 써야 하는데 좀 까다로운 문제입니다.

매 회 수 마다 이모티콘 수 -1, 클립보드 복사, 클립보드 붙여넣기의 세 가지 경우의 수로 queue에 push 해야 되지만,

현재 이모티콘의 수와 클립보드에 저장된 이모티콘의 수에 따라 경우의 수가 모두 달라지기 때문에

vis[현재 화면의 이모티콘 수][클립보드에 저장된 이모티콘 수]

로 bfs를 해주는 게 이 문제의 솔루션입니다!

---

Description

두 개의 pair를 써서 세 개의 변수를 queue에 담습니다. (현재 값, 클립보드 저장 값, 횟수 값)

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int n,res;
int vis[1001][1001]; // vis[현재 화면의 이모티콘 수][클립보드에 저장된 이모티콘 수]
queue < pair<int, pair<int, int>>> q; // 두 개의 pair를 써서 세 개의 변수를 queue에 담았습니다.
int main(void) {
    scanf("%d", &n);
    memset(vis, -1, sizeof(vis));
    vis[1][0] = 1;
    q.push({ 1,{0,0} });
    while (!q.empty()) {
        int now = q.front().first;
        int save = q.front().second.first;
        int cnt = q.front().second.second;
        if (now == n) {  // 원하는 수를 queue에서 찾으면 바로 break를 해 최소 횟수 값을 출력합니다.
            res = cnt;
            break;
        }
        q.pop();
        if (vis[now - 1][save] == -1) {
            if (now - 1 > 0) {
                vis[now - 1][save] = 1;
                q.push({ now - 1,{save,cnt + 1} });
            }
        }
        if (vis[now][now] == -1) {
            vis[now][now] = 1;
            q.push({ now,{now,cnt + 1} });
        }
        if (save != 0) {
            if (now+save<=1000) {
                if (vis[now + save][save] == -1) {
                    vis[now + save][save] = 1;
                    q.push({ now + save,{save,cnt + 1} });
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}