[BOJ] 14226 : 이모티콘

풀이

BFS

check배열을 [현재이모티콘] [클립보드값] 이렇게 2차원으로 둔다.

그리고는 3가지 상황에 대해서 조건이 맞으면 체크하고 큐에 넣는

BFS탐색을 진행하면 된다.

1: 이모티콘 모두복사 후 클립보드 저장

d[e][c] -> d[e][e]

2: 클립보드 이모티콘 화면에 붙여넣기

d[e][c] -> d[e+c][c]

3. 화면에 있는 이모티콘 중 하나를 삭제

d[e][c] -> d[e-1][c]

코드

#include <iostream>
#include <queue>
#include <tuple>

#define MAX_NUM 1000

using namespace std;

//현재 위치, 복사된거, 시간
typedef tuple<int, int, int> my_t;

bool check[1001][1001];
int s;

int main() {
    
    cin >> s;
    
    check[1][0] = true;
    queue<my_t> q;
    q.push({ 1, 0, 0 });
    
    int cur, time, copy, next;
    while (!q.empty()) {
        tie(cur, copy, time) = q.front();
        
        if (cur == s) {
            cout << time << endl;
            break;
        }
        
        if (cur != copy) {
            q.push({ cur, cur, time + 1 });
        }
        
        if (copy != 0) {
            next = cur + copy;
            if (next <= MAX_NUM) {
                if (!check[next][copy]) {
                    check[next][copy] = true;
                    q.push({ next, copy, time + 1 });
                }
            }
        }
        
        next = cur - 1;
        if (next >= 0) {
            if (!check[next][copy]) {
                check[next][copy] = true;
                q.push({ next, copy, time + 1 });
            }
        }
        
        q.pop();
    }
    
    return 0;
}

Written on April 1, 2019