[백준/C++] 14226 이모티콘

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

코드

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

#define MAX 1001
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);

int s;
bool visited[MAX][MAX]; 

struct d {
    int cnt;
    int clip; 
    int time; 
};

void bfs() {
    queue<d> q;
    q.push({ 1, 0, 0 }); 
    visited[1][0] = 1;

    while (!q.empty()) {
        int cnt = q.front().cnt;
        int clip = q.front().clip;
        int time = q.front().time;
        q.pop();

        if (cnt == s) {
            cout << time;
            return;
        }

        if (visited[cnt][cnt] == 0) {
            visited[cnt][cnt] = true;
            q.push({ cnt, cnt, time + 1 });
        }

        if (clip > 0 && cnt + clip < MAX && visited[cnt + clip][clip] == 0) {
            visited[cnt + clip][clip] = true;
            q.push({ cnt + clip, clip, time + 1 });
        }
        if (cnt - 1 >= 0 && visited[cnt - 1][clip] == 0) {
            visited[cnt - 1][clip] = true;
            q.push({ cnt - 1, clip, time + 1 });
        }
    }
}

int main() {
    FASTIO;
    cin >> s;
    bfs();
    return 0;
}

설명

현재 화면에 있는 이모티콘 수와 클립보드에 있는 이모티콘 수를 가지고 BFS를 돌리면 됩니다. 1~3번의 상황을 각각 IF문으로 구현하고, cnt가 s일 때의 시간을 출력합니다.

 

느낀 점

BFS로 풀이했습니다.