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

www.acmicpc.net/problem/14226

14226번: 이모티콘

BFS와 DP를 이용한 문제 (다시 풀기)

화면과 클립보드를 가진 2차원 visit 배열을 선언하여 방문 여부를 확인하고 그 값으로 시간을 기록하는 것이 포인트입니다. 또한 클립보드의 내용을 화면에 출력하는 과정에서 '화면 + 클립보드 < 입력값의 최대' 조건을 반드시 만족해야 런타임 에러가 발생하지 않습니다. 

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int visit[1001][1001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int s;
    cin>>s;
    
    memset(visit, -1, sizeof(visit)); // 초기화
    queue<pair<int ,int > > q;
    q.push({1, 0}); // 화면, 클립보드
    visit[1][0] = 0;
    
    while(!q.empty()) {
        int dis = q.front().first;
        int clip = q.front().second;
        q.pop();
        
        if(dis == s) {
            cout<<visit[dis][clip];
            break;
        }
       
        // 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장
        if(visit[dis][dis] == -1) {
            q.push({dis, dis});
            visit[dis][dis] = visit[dis][clip] + 1;
        }
    
        // 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
        if(dis + clip < 1001 && visit[dis + clip][clip] == -1) {
            q.push({dis + clip, clip});
            visit[dis + clip][clip] = visit[dis][clip] + 1;
        }
    
        // 화면에 있는 이모티콘 중 하나를 삭제
        if(dis > 0 && visit[dis - 1][clip] == -1) {
            q.push({dis - 1, clip});
            visit[dis - 1][clip] = visit[dis][clip] + 1;
        }
    }
}