백준 및 코드포스

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();
}

태그는 백트래킹이다.
하지만 내 맥북의 vscode에서 pair 기능이 작동하지 않아서 pair를 사용하지 않고 풀었다.
메모리 제한이 작으며, 8자리 수까지 판별하는 문제라 에라토스테네스의 체를 사용할 수는 없다.

내가 푼 방법이다.

0. 한 자리 소수는 2, 3, 5, 7 뿐이다.
=> 큐에 2, 3, 5, 7을 넣어준다.

1. 큐에 담긴 n자리 소수의 뒷자리에 1,3,7,9를 넣어서 n + 1자리의 숫자를 만든다.

1 ~ 3의 과정을 n - 1번 반복하면 n자리 수의 소수만 큐에 남는다.

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

int dx[4] = {1,3,7, 9};
int n, ans;
queue <int> Q;

void Prime() {
    int size = Q.size();
    while(size--){
        for(int i = 0; i < 4; i++) {
            bool isPrime = 1;
            int cur = Q.front() * 10 + dx[i];

            for(int j = 3; j <= sqrt(cur); j++) {
                if(cur % j == 0){ 
                isPrime = 0;
                break;
                }
            }
            if(isPrime) {
                Q.push(cur);
            }
        }
        Q.pop();
    }
}

int main() {
    Q.push(2);
    Q.push(3);
    Q.push(5);
    Q.push(7);
    cin>>n;

    for(int i = 1; i < n; i++) {
        Prime();
    }
    
    ans = Q.size();
    for(int i = 0; i < ans; i++) {
        cout<<Q.front()<<'\n';
        Q.pop();
    }
}

문제가 길어서 따로 사진을 첨부하진 않겠습니다.

직접 들어가서 읽어보시는 걸 추천드립니다.

결과적으로 구해야 하는 것은 바깥쪽의 공기와 치즈가 2번 이상 만나는지 입니다.

제 풀이 방법입니다.
1. 가장자리는 무조건 공기니까, 매번 (0,0)을 큐에 넣어준다.
2. 치즈 밖에 있는 공기만으로 공기의 접촉을 계산하니, bfs를 돌리며 치즈와 외곽의 공기가 만나면 1씩 더해준다.
3. 치즈가 공기와 2번 이상 접촉했으면 치즈를 공기로 바꿔준다.
4. vis 배열을 초기화 시킨 후, 1번부터 반복한다.

치즈가 전부 사라질 때까지 이를 반복해서 풀 수 있습니다.

코드에서 주석으로 핵심 ~,  ~  핵심 으로 표시해둔 부분이 다른 문제와 다른 부분입니다.

방문 여부만으로 continue를 시켜주면 치즈에 공기가 한 번만 닿고 그 이후엔 continue 되어 문제 해결이 불가능합니다.

치즈와 공기를 따로 생각해줘야합니다.

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

int board[101][101];
int vis[101][101];
int dx[4] = {1,-1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;
int ans = -1,check = 1;
queue<pair<int,int> > Q;

void bfs() {
    check = 0;
            Q.push({0, 0}); //가장자리는 항상 공기임
            while(!Q.empty()){
                pair<int,int> cur = Q.front();
                Q.pop();
                int nx, ny;
                for(int dir = 0; dir < 4; dir++){
                    nx = cur.first + dx[dir];
                    ny = cur.second + dy[dir];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if(!board[nx][ny] && vis[nx][ny]) continue; //핵심 ~
                    if(board[nx][ny]) {
                        vis[nx][ny]++;
                        check = 1;
                        continue;
                    } // ~ 핵심
                    if(vis[nx][ny]) continue;
                    vis[nx][ny]++;
                    Q.push({nx,ny});
                }
            }
 
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(vis[i][j] >= 2) board[i][j] = 0; //2번 이상 접촉시 치즈가 녹음
            vis[i][j] = 0; //방문 초기화
        }
    }
    ans++;
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin>>board[i][j];
        }
    }

    while(check) { //check는 배열 board 안에 치즈가 남았는지 확인
        bfs();
    }
    cout<<ans;
}

https://codeforces.com/contest/1742