백준(boj)14226 - 이모티콘

문제 링크 - https://www.acmicpc.net/problem/14226

👀문제이해 및 풀이방법

dp분류에 있는 문제인데 사실상 bfs 문제이다 q를 2개 선언해서 다음bfs에 들어갈 목록을 업데이트하며 bfs를 돌려주면 된다
전역변수로 q를 하나 선언했고 nq를 bfs에서 채워 마지막에 q에 넣는 형식으로 구성하였다
코드를 보면 어렵지 않게 풀 수 있는 문제이다

📝코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class imoticon{
private:
    queue<pair<int,int>> q;
    vector<vector<bool>> visit;
    int S;
public:
    imoticon(){
        std::cin >> S;
        visit.resize(S*2,vector<bool>(S*2,false));
        q.push({1,0});
    }
    bool bfs(){
        queue<pair<int,int>> nq;
        pair<int,int> cur;
        while(!q.empty()){
            cur = q.front();
            q.pop();
            if(cur.first==S)
                return true;
            if(!visit[cur.first][cur.first]){
                visit[cur.first][cur.first]=true;
                nq.push({cur.first,cur.first});
            }
            if(cur.first+cur.second<S*2){
                if(!visit[cur.first+cur.second][cur.second]){
                    visit[cur.first+cur.second][cur.second]=true;
                    nq.push({cur.first+cur.second,cur.second});
                }
            }
            if(cur.first>1 && !visit[cur.first-1][cur.second]){
                visit[cur.first-1][cur.second]=true;
                nq.push({cur.first-1,cur.second});
            }
        }
        q=nq;
        return false;
    }
    void find_sol(){
        int sol =0;
        visit[1][0]=true;
        while(!bfs())
            sol++;

        std::cout << sol << '\n';
    }
};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    imoticon imc;
    imc.find_sol();

    return 0;
}