백준 및 코드포스

bfs 문제이다.

{ 복사, 붙여넣기, 삭제 }의 3가지 경우의 수에 따라서 bfs를 돌려주면 된다.

나는 두 가지 방법으로 풀었다.

첫 번째 방법이다.

1. 미리 탐색을 끝마친다.

2. S개의 이모티콘을 만드는데에 가장 짧은 시간을 출력한다.

vis배열을 2차원으로 선언해서,

n개의 이모티콘이 클립보드에 있을 때

1000개의 이모티콘을 만드는 가장 짧은 시간을 탐색한다.

이 방법은 미리 탐색을 전부 다 하는 방법이다.

그래서 28ms로, 두 번째 방법보다 시간이 오래 걸렸다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
queue<pair<int, int> > Q;
int arr[1001][1001], vis[1001][1001] = {1};

void func() {
    while(!Q.empty()) {
    pair<int, int> cur = Q.front();Q.pop();
        int nx = cur.first;
        int ny = cur.second;//clipboard
        if(nx - 1 > 0 && !vis[nx - 1][ny]) {//삭제
            vis[nx - 1][ny] = vis[nx][ny] + 1;
            Q.push({nx - 1, ny});
        }
        if(nx <= 1000 && !vis[nx][nx]) {//복사
            vis[nx][nx] = vis[nx][ny] + 1;
            Q.push({nx, nx});
        }
        if(nx + ny <= 1000 && !vis[nx + ny][ny]) {//붙여넣기
            vis[nx + ny][ny] = vis[nx][ny] + 1;
            Q.push({nx + ny, ny});
        }
    }
}

int main() {
	int n;
    cin>>n;
    Q.push({1, 0});
    func();
    int ans = 109283471;
    for(int i = 1; i <= 1000; i++) {
        ans = min(ans, vis[n][i]); //최솟값 찾기
    }
    cout<<ans;
}

두 번째 방법이다.

1. 탐색을 하면서 S개의 이모티콘이 만들어졌는지 확인한다.

2. S개의 이모티콘이 만들어졌다면 바로 출력하고 종료한다.

가중치가 1로 동일한 bfs이기에,

S개의 이모티콘이 처음 만들어진 시점이 최단시간이라는 것이 보장된다.

코드도 더 깔끔하고, 4ms로 빠른 풀이이다.

void func() {
    while(!Q.empty()) {
    pair<int, int> cur = Q.front();Q.pop();
        int nx = cur.first;
        int ny = cur.second;//clipboard
        if(nx == n) { //S개의 이모티콘 찾으면 바로 출력
            cout<<vis[nx][ny];
            return;
        }
        if(nx - 1 > 0 && !vis[nx - 1][ny]) { //삭제
            vis[nx - 1][ny] = vis[nx][ny] + 1;
            Q.push({nx - 1, ny});
        }
        if(nx <= 1000 && !vis[nx][nx]) { //복사
            vis[nx][nx] = vis[nx][ny] + 1;
            Q.push({nx, nx});
        }
        if(nx + ny <= 1000 && !vis[nx + ny][ny]) { //붙여넣기
            vis[nx + ny][ny] = vis[nx][ny] + 1;
            Q.push({nx + ny, ny});
        }
    }
}

int main() {
    cin>>n;
    Q.push({1, 0});
    func();
}