[백준] 14226. 이모티콘 풀이

Problem

14226. 이모티콘

Approach

전형적인 bfs 문제.

큐에 들어가는 element의 자료구조: \( { { 현재 이모티콘 수, 클립보드의 이모티콘 수 } , operation 횟수 } \)

\( \{ \{ 1, 0 \} , 0 \}\) 에서 시작해서, 각 단계에서 아래의 탐색공간들을 추가로 탐색.

\(s := 현재 이모티콘 수\)
\(clip := 클립보드의 이모티콘 수\)
\(o := operation 횟수\)

• \(s = S\) 이면 \(o\) 값을 출력, 종료
• \(s \gt 1\) 이고 \(visited[s-1][clip] = false\) 이면 \(\{\{ s-1, clip\} , o+1\}\)를 탐색
• \(s + clip \le 1001\) 이고 \(visited[s+clip][clip] = false\) 이면\( \{ \{ s+clip, clip \} , o+1 \}\)를 탐색
• \(visited[s][s] = false\) 이면 \(\{ \{ s, s \} , o+1 \}\)를 탐색

Code

/**
 * author: jooncco
 * written: 2021. 2. 27. Sat. 22:23:27 [UTC+9]
 **/

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <cmath>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef deque<int> di;
typedef deque<ii> dii;

const int LIMIT= 1001;

int S;
bool visited[1010][1010]= {0};

int main() {

    FAST_IO;
    cin >> S;

    queue<pair<ii,int>> Q;
    Q.push(make_pair({1,0},0));
    int ans= 0;
    while (!Q.empty()) {
        pair<ii,int> cur= Q.front(); Q.pop();
        int s= cur.first.first, clip= cur.first.second;
        int cnt= cur.second;

        if (s == S) {
            ans= cnt;
            break;
        }

        if ( s+clip <= LIMIT && !visited[s+clip][clip] ) visited[s+clip][clip]= 1, Q.push( make_pair({s+clip,clip}, cnt+1) );
        if ( !visited[s][s] ) visited[s][s]= 1, Q.push( make_pair({s,s}, cnt+1));
        if ( s > 1 && !visited[s-1][clip] ) visited[s-1][clip]= 1, Q.push( {make_pair(s-1,clip}, cnt+1) );
    }

    cout << ans;
}

Complexity

• Time: \(O(S^2)\)
• Space: \(O(S^2)\)