BOJ 1963 소수 경로 / BOJ 1240 노드 사이의 거리 / BOJ 11779 최소비용 구하기 2

백준 BOJ 1963번 : 소수 경로

Solved.ac 난이도 : Gold IV

알고리즘 분류 : 에라토스테네스의 체, BFS

 

주어진 네 자리 소수 A를 다른 소수 B로 바꿀 때, 한 자리씩 바꾸는 동시에 소수임을 유지하면서 B로 바꾸기 위해서는 최소 몇 번의 자리 교체가 이루어져야 하는지를 구하는 문제입니다.

 

네 자리 수의 개수는 9000개 정도 밖에 되지 않으므로, 당연히 완전 탐색이 가능한 문제입니다.

다만 "최소" 교체 수를 구하기 위해서 BFS를 이용하여 구현을 해주면 됩니다.

 

소수 판별을 여러 번 해야하기 때문에 에라토스테네스의 체를 활용하여 소수를 미리 구해놓으면 편합니다.

또한 string과 int 사이의 변환이나 맨 앞 자리 수가 0이 나와서 세 자리 수가 되지 않는지 체크를 해주면서 코드를 작성해야 합니다.

나머지는 간단한 BFS로써 구현이 쉽게 가능합니다.

 

 

#include <bits/stdc++.h>
#define MAX 10000
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    bool prime[MAX] = {};
    for(int i=2; i<MAX; i++) prime[i] = true;
    for(int i=2; i*i<MAX; i++)
        for(int j=2; i*j<MAX; j++) prime[i*j] = false;

    int T; cin >> T;

    while(T--) {
        string from, to; cin >> from >> to;

        queue<string> Q;
        Q.push(from);

        int cnt[MAX] = {};
        for(int i=0; i<MAX; i++) cnt[i] = -1;
        cnt[stoi(from)] = 0;

        while(!Q.empty()) {
            string curr = Q.front();
            Q.pop();

            if(curr == to) break;

            for(int i=0; i<4; i++)
                for(int j=0; j<10; j++) {
                    string temp = curr;
                    temp[i] = j + '0';
                    int next = stoi(temp);

                    if(next < 1000 || !prime[next]) continue;
                    if(cnt[next] != -1) continue;

                    cnt[next] = cnt[stoi(curr)] + 1;
                    Q.push(temp);
                }
        }

        cout << cnt[stoi(to)] << "\n";
    }
}

 

 

백준 BOJ 1240번 : 노드 사이의 거리

Solved.ac 난이도 : Gold V

알고리즘 분류 : 다익스트라

 

N(≤1000)개의 노드로 이루어진 트리와 M개의 노드 쌍을 입력받을 때 두 노드 사이의 거리들을 순서대로 출력하는 문제입니다.

 

노드와 간선의 수가 많지 않으므로 M개의 순서쌍 각각에 대해서 최단 거리를 따로 구해줘도 됩니다. (플로이드-와셜 알고리즘과 같이 한 번에 구할 필요가 없다는 뜻)

따라서 M개의 쌍에 대한 다익스트라를 반복문으로써 구현해주면 AC를 받을 수 있습니다.

 

주의할 부분은 다익스트라 수행 과정에서 dist[next] != -1으로 이미 next 노드까지의 거리가 구해져있다면 continue를 통해 queue에 넣어주지 않도록 해야한다는 것입니다.

그렇지 않으면 queue에 쓸데없는 노드들이 너무 많이 저장되어 메모리 초과가 발생할 수 있습니다.

 

 

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;

vector<pair<int, int>> adj[MAX]; // adj[from] = <to, distance>

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    for(int i=0; i<N-1; i++) {
        int from, to, dist_; cin >> from >> to >> dist_;

        adj[from].push_back({to, dist_});
        adj[to].push_back({from, dist_});
    }

    while(M--) {
        int sour, dest; cin >> sour >> dest;

        int dist[MAX];
        for(int i=1; i<=N; i++) dist[i] = -1;

        queue<int> Q;
        Q.push(sour);
        dist[sour] = 0;

        int sum = 0;
        while(!Q.empty()) {
            int curr = Q.front();
            Q.pop();

            if(curr == dest) break;

            for(int i=0; i<adj[curr].size(); i++) {
                int next = adj[curr][i].first;
                int dist_ = adj[curr][i].second;

                if(dist[next] != -1) continue;

                dist[next] = dist[curr] + dist_;
                Q.push(next);
            }
        }

        cout << dist[dest] << "\n";
    }
}

 

 

 

백준 BOJ 11779번 : 최소비용 구하기 2

Solved.ac 난이도 : Gold III

알고리즘 분류 : 다익스트라

 

도시의 개수와 경로의 개수가 주어지고, 각 경로의 시작점과 도착점 그리고 비용이 주어진다고 할 때, 특정 도시에서 도시로 가는 경로의 최소 비용을 구하는 문제입니다.

 

가장 정석적인 형태의 다익스트라 문제입니다.

범위가 작지는 않으므로 시간 초과에 주의하여 효율적으로 다익스트라 알고리즘을 구현해주면 됩니다.

 

 

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;

typedef pair<int, int> Pair;

vector<Pair> adj[MAX]; // adj[from] <to, distance>
int dist[MAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    while(M--) {
        int from, to, dist_; cin >> from >> to >> dist_;

        adj[from].push_back({to, dist_});
    }

    int sour, dest; cin >> sour >> dest;

    for(int i=1; i<=N; i++) dist[i] = INT_MAX;
    dist[sour] = 0;

    priority_queue<Pair, vector<Pair>, greater<Pair>> PQ; // <distance, node>
    PQ.push({0, sour});

    int prev[MAX];
    for(int i=1; i<=N; i++) prev[i] = -1;

    while(!PQ.empty()) {
        int dist1 = PQ.top().first;
        int curr = PQ.top().second;
        PQ.pop();

        if(dist[curr] < dist1) continue;

        for(int i=0; i<adj[curr].size(); i++) {
            int next = adj[curr][i].first;
            int dist2 = adj[curr][i].second;

            if(dist1 + dist2 < dist[next]) {
                dist[next] = dist1 + dist2;
                PQ.push({dist[next], next});
                prev[next] = curr;
            }
        }
    }

    cout << dist[dest] << "\n";

    vector<int> route;
    int curr = dest;
    while(curr != -1) {
        route.push_back(curr);
        curr = prev[curr];
    }

    cout << route.size() << "\n";
    for(int i=route.size()-1; i>=0; i--)
        cout << route[i] << " ";
    cout << "\n";
}

 

보통은 우선순위 큐를 이용하되 비용을 -cost로 저장하여 작은 비용이 먼저 나오도록 하였으나, 저는 그냥 우선순위 큐를 활용하여 코드를 직관적으로 이해하기 수월하게 구현해봤습니다.

그리고 큐에서 경로를 꺼낼 때 dist[curr] < continue;를 해주어 다음의 반복문에서 큐에 쓸데없는 도시들이 계속 들어가지 않도록 해줍니다. (그렇지 않으면 시간 초과가 발생합니다.)