알고리즘 :: 백준 :: BFS :: 14226 :: 이모티콘

문제

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

문제접근

• 이모티콘의 개수를 정점 으로 생각하면, 최적해를 구하기 위해 BFS를 사용해야 함을 알 수 있다. (물론, 모든 경우 탐색 + 최적해를 보고 Bruteforce 또는 DP도 생각할 수 있다.)
• 모든 연산이 1초가 걸리므로 가중치는 1이다. 따라서 BFS를 쓸 수 있다.
• 그러나, 단순히 이모티콘의 개수를 정점으로 생각하면 안된다.
  • 왜냐하면, 이모티콘 x개에서 다음 연산 결과로 나오는 이모티콘의 개수는 x개, ?개, x-1개 세 개 중 하나인데, ?개가 몇 개인지는 클립보드에 저장된 이모티콘 개수에 따라 다르기 때문이다! (DP로 풀었다면 2차원 메모이제이션을 사용했을 것이다.)
• 그러므로, 정점은 [화면에 표시된 이모티콘의 개수][클립보드에 저장된 이모티콘 개수]의 2차원 배열로 표시해야 맞다.

코드

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

static constexpr int MAX = 100001;
static int subin, brother, map[MAX], from[MAX], dist[MAX];
static bool isVisited[MAX];

void backTracking(int subin, int pos) {
    // subin (출발지점) 까지 백트랙킹 한다.
    if (subin != pos) backTracking(subin, from[pos]);
    cout << pos << ' ';
}

void solve() {
    queue<int> q;
    q.push(subin);
    isVisited[subin] = true;
    dist[subin] = 0;

    while(!q.empty()) {
        int pos = q.front(); q.pop();
        int goPos = pos + 1, backPos = pos - 1, telePos = pos * 2;
        // 한 칸 앞으로 전진하는 경우
        if (goPos < MAX && isVisited[goPos] == 0) {
            q.push(goPos);
            isVisited[goPos] = true;
            dist[goPos] = dist[pos] + 1;
            from[goPos] = pos;
        }
        // 한 칸 뒤로 후진하는 경우
        if (backPos >= 0 && isVisited[backPos] == 0) {
            q.push(backPos);
            isVisited[backPos] = true;
            dist[backPos] = dist[pos] + 1;
            from[backPos] = pos;
        }
        // 2배 앞으로 순간이동 하는 경우
        if (pos != 0 && telePos < MAX && isVisited[telePos] == 0) {
            q.push(telePos);
            isVisited[telePos] = true;
            dist[telePos] = dist[pos] + 1;
            from[telePos] = pos;
        }
    }
    cout << dist[brother] << '\n';
    backTracking(subin, brother);
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> subin >> brother;
    solve();
}

결과