[C++] 소프티어: 지우는 소수를 좋아해

🔗 문제

https://softeer.ai/practice/info.do?idx=1&eid=582 

Softeer

 

✏️ 풀이

 

다익스트라 문제다.

(1) 출발 지점이 주어져있고, (2) 양방향이며, (3) 가중치가 양수다.

무엇보다 출발 지점에서 특정지점까지 필요한 값을 출력해야한다는게 다익스트라문제라는 큰 힌트다.

 

다익스트라를 학습할 때 주로 사용하는 최소 경로가 아니라 최소 레벨을 구해야하는게 작은 차이일 뿐이다.

정석 다익스트라 풀이로 priority_queue를 이용했다.

• dp[node]에 1에서 node까지 가는 가장 큰 레벨을 저장한다.

 

 

문제의 제약조건을 보면 총 노드의 수는 $2 ≤ N ≤ 10,000$ 로 한정되어 있다.

가중치를 가지는 그래프를 저장하는 두가지 방법과 각 장단점을 간단하게 적자면..

1. 이차원 배열을 활용 (solve2)
   1. 연결된 간선에는 가중치를 저장한다.
   2. 연결되지 않은 간선에는 2 미만의 값
2. 연결된 간선 정보만 저장 (solve)

 

당연한 소리하는 구간

1. 이차원 배열을 활용하면 map[current_node][next_node] = weight로 직관적인 파악이 가능하다는 장점이 있다. 단점으로는 굉장히 많은 메모리를 차지하고 연결 유무를 노드수 만큼 반복해야 하기 때문에 탐색 시간도 많이 걸린다. 
2. 연결된 간선 정보만 저장한다면 메모리와 시간을 아낄 수 있다는 장점이 있지만 라이브러리에 익숙하지 않으면 힘들 수도 있다. 하지만 방법 1이 너무 별로니까 극복해야죠 뭐…

 

제가 제약 조건을 고려하지 않고 이차원 배열로 10000 x 10000번 찾는 짓하다가 런타임에러와 오류를 봐서 쓰는 포스팅입니다.

저처럼 방법 1 (아래 소스의 solve2 함수) 을 고수하면서 왜 오답인지 답답해하시는 분에게 도움이 되기 바라며 이만 총총..

 

 

+) 정답은 소수여야 한다는 점..  그리고 체육관레벨 <= 지우 레벨 이 아니라 체육관 레벨 < 지우 레벨이어야 한다는 사실도 잊지 않기!

 

💾  소스

#include <iostream>
#include <queue>
#include <vector>

typedef long long ll;
typedef std::pair<int, int> pii;

const int MAX = 10000 + 1;

int N, M;
std::vector<ll> dp;
std::vector<pii> adj[MAX];
int map[MAX][MAX] = {0, };

bool isPrime(const ll x)
{
    if(x < 2) return false;
    
    for(ll i=2; i*i<=x; ++i)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}

void solve2(const int start) // by arr[][]
{

    //input
    int a, b, c;
    std::cin >> N >> M;
    dp.resize(N+1, 1e9);
    while(M--)
    {
        std::cin >> a >> b >> c;
        map[a][b] = map[b][a] = c;
    }

    //solve
    std::priority_queue<pii> pq;

    pq.push({0, start});
    dp[start] = 0;
 
    while(!pq.empty())
    {
        int level = -pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if(dp[node] != level) continue;
 
        for(int next_node=1; next_node<=N; ++next_node)
        {
            if(map[node][next_node] == 0) continue;

            int next_level = map[node][next_node];
            ll max_level = (next_level > level ? next_level : level);
            if(max_level < dp[next_node])
            {
                dp[next_node] = max_level;
                pq.push({-max_level, next_node});
            }
        }
    }
}

void solve(const int start)
{
    // input
    int u, v, c;
    std::cin >> N >> M;
    dp.resize(N+1, 1e9);
    while(M--)
    {
        std::cin >> u >> v >> c;
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }

    std::priority_queue<pii> pq;

    pq.push({0, start});
    dp[start] = 0;
 
    while(!pq.empty())
    {
        int level = -pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if(dp[node] != level) continue;
 
        for(const auto& [next_node, next_level] : adj[node])
        {
            int max_level = (next_level > level ? next_level : level);
            if(max_level < dp[next_node])
            {
                dp[next_node] = max_level;
                pq.push({-max_level, next_node});
            }
        }
    }
}

int main()
{

    solve(1);
    
    for(ll i=dp[N]+1; ;++i)
    {
        if(isPrime(i))
        {
            std::cout << i;
            return 0;
        }
    }

    return 0;
}