[algorithm] 백준 - 이모티콘

weight가 제 각각일 경우 dijkstra로 최솟값을 구할 수 있고,
1로 일정할 경우엔 bfs로 최솟값을 구할 수 있다.

이 문제는 범주가 3개로 나뉜다.

1. 화면에 이모티콘 붙여넣기
   
   화면 이모티콘 개수 + 클립보드 이모티콘 개수

 

2. 화면에 이모티콘 삭제
   
   화면 이모티콘 개수 - 1

 

3. 화면에 이모티콘 복사하기
   
   클립보드 이모티콘 개수 = 화면 이모티콘 개수

화면 이모티콘과 클립보드 이모티콘 개수를 따로 기록해줘야하므로
pair를 이용해서 queue에 집어넣었다.

//백준 이모티콘
#include <iostream>
#include <queue>
using namespace std;

int weight[1001][1001];
bool visited[1001][1001];
int answer = 0;
void initWeight(){
    for(int i = 0; i <= 1000; i++){
        for(int j = 0; j <= 1000; j++){
            weight[i][j] = 0;
        }
    }
}
void initVisited(){
    for(int i = 0; i <= 1000; i++){
        for(int j = 0; j <= 1000; j++){
            visited[i][j] = false;
        }
    }
}
void bfs(int s){
    queue<pair<int,int>> q;
    q.push({1,0});
    while(!q.empty()){
        pair<int,int> node = q.front();
        q.pop();
        if(node.first == s){
            answer = weight[node.first][node.second];
            return;
        }
        if(!visited[node.first][node.first]){
            weight[node.first][node.first] = weight[node.first][node.second] + 1;
            visited[node.first][node.first] = true;
            q.push({node.first, node.first});
        }
        int imojiNumAfterPaste = node.second + node.first;
        if(imojiNumAfterPaste <= 1000 && !visited[imojiNumAfterPaste][node.second]){
            weight[imojiNumAfterPaste][node.second] = weight[node.first][node.second] + 1;
            visited[imojiNumAfterPaste][node.second] = true;
            q.push({imojiNumAfterPaste, node.second});
        }
        int imojiNumAfterAbandon = node.first - 1;
        if(imojiNumAfterAbandon >= 2 && !visited[imojiNumAfterAbandon][node.second]){
            weight[imojiNumAfterAbandon][node.second] = weight[node.first][node.second] + 1;
            visited[imojiNumAfterAbandon][node.second] = true;
            q.push({imojiNumAfterAbandon, node.second});
        }
    }
}
int main(void){
    int s;
    cin >> s;
    bfs(s);
    cout << answer;
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102905.cpp

jeongdaeun98/algorithm