백준 14226번 : 이모티콘 - BFS

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

14226번: 이모티콘

1. 문제설명

한 번에 3가지 연산을 할 수 있다.

screen과 clipboard의 정보를 저장해서 BFS를 수행하면

원하는 이모티콘의 개수를 만들기 위한 최소 단계를 구할 수 있다.

 

 

---

 

2. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
#define MAX_NUM 2003


int s;
struct Emoticon{
    int screen, copied;
};

int vis[MAX_NUM][MAX_NUM];

int BFS(int x){
    queue<Emoticon> Q;
    Q.push({1,0}); vis[1][0] = 1;

    while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        int curValue = vis[cur.screen][cur.copied];

        if(cur.screen == x){
            return curValue - 1;
        }


        //1. 클립보드에 복사하여 저장
        if(!vis[cur.screen][cur.screen]){
            vis[cur.screen][cur.screen] = curValue + 1;
            Q.push({cur.screen, cur.screen});
        }

        //2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.,클립보드는 그대로 유지
        if(cur.screen+ cur.copied < MAX_NUM && !vis[cur.screen+cur.copied][cur.copied]){
            vis[cur.screen+cur.copied][cur.copied] = curValue + 1;
            Q.push({cur.screen + cur.copied, cur.copied});
        }

        //3. 화면에 있는 이모티콘 중 하나를 삭제한다.
        if(cur.screen-1 > 0 && !vis[cur.screen-1][cur.copied]){
            Q.push({cur.screen-1, cur.copied});
            vis[cur.screen-1][cur.copied] = curValue + 1;
        }

    }

    return -1;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    cout << BFS(s) << '\n';

    return 0;
}

 

나는 BFS로 이 문제를 풀었는데

DP로도 이 문제를 풀 수 있다.

 

BFS와 DP의 교집합에 놓인 문제라면

DP가 규칙만 빠르게 발견하면 훨씬 간결하게

풀 수 있는 장점이 있는 것 같다.

 

시간 절약을 위해 DP 공부를 더 해야할 필요가 있어보인다.