BOJ : 14226 이모티콘

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

간단한 BFS이지만 visited 배열을 잘 활용하지 못한다면 원하는 정답이 안나올 것이다.

현재 글자수 뿐만아니라 클립보드에 저장 돼 있는 글자 수도 고려해줘야 한다.

핵심 visited[글자수][클립보드]

#include <cstdio>
#include <queue>
using namespace std;
int S,cnt=0;
queue<pair<int, int>> q;
bool visited[2002][2002];
int main(){
    scanf("%d",&S);
    q.push(make_pair(1, 0));
    visited[1][0]=1;
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            int len = q.front().first;
            int clip = q.front().second;
            q.pop();
            
            if(len == S){
                printf("%d\n",cnt);
                return 0;
            }
            
            //1. copy
            int c = len;
            q.push(make_pair(len, c));
            
            //2. paste
            if(clip!=-1) {
                int l = len+clip;
                if(!visited[l][clip] && l<=1000) q.push(make_pair(l, clip));
                visited[l][clip] = 1;
            }
            
            //3. remove emoji
            int l = len-1;
            if(!visited[l][clip] && l>1) q.push(make_pair(l, clip));
            visited[l][clip] = 1;
        }
        cnt++;
    }
}