백준 14226 - 이모티콘 (C++)

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

14226번: 이모티콘

 

풀이 

일단 최소시간이니까 bfs로 풀어야겠다고 생각했고,

계속 가지고 다닐 값이 총 3개(화면에 있는 이모티콘 개수, 클립보드에 있는 이모티콘 개수, 시간)라서 tuple을 사용했다.

처음엔 방문배열을 1차원으로 만들어서 답이 잘 안 나왔다.

방문배열을 현재 화면과 클립보드 2개를 체크하도록 2차원으로 수정했는데 그래도 틀림..

 

문제는 이모티콘 최대 길이를 잘못 생각한 것이었다.

S가 최대 1000이라서 최댓값을 1000으로 했는데,

클립보드에서 복사-붙여넣기하면 길이가 최대 2000이 될 수 있다. 

따라서 최대값을 2000으로 변경하여 풀이했고 성공!

 

일반적인 bfs와 다른 점은 방문배열이 2차원이라는 것, 큐에 저장할 값이 3개라는 것이었다~

 

코드

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

int S, res = 987654321;
bool visited[2000][2000];

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

    while (!q.empty()) {
        int curDis = get<0>(q.front());
        int curClip = get<1>(q.front());
        int curTime = get<2>(q.front());
        if (curDis == S) {
            res = min(res, curTime);
        }
        q.pop();
        if (curDis + curClip >= 2000 || curDis <= 0) continue;
        if (!visited[curDis][curDis]) {
            visited[curDis][curDis] = true;
            q.push({curDis, curDis, curTime + 1});
        }

        if (curClip != 0 && !visited[curDis + curClip][curClip]) {
            visited[curDis + curClip][curClip] = true;
            q.push({curDis + curClip, curClip, curTime + 1});
        }
        if (!visited[curDis - 1][curClip]) {
            visited[curDis - 1][curClip] = true;
            q.push({curDis - 1, curClip, curTime + 1});
        }
    }

}

int main() {
    cin >> S;
    bfs();
    cout << res;
}