[백준] 1800번 인터넷 설치

백준: 1800: 인터넷 설치

1800번: 인터넷 설치

상당히 오랫동안 블로그 업로드나 알고리즘 풀이를 오랫동안 쉬었다. 아무래도 직장에 들어가면서 자연스레 나태해진 탓일까...

사실 회사 내 보안이 철저해서 사진 하나 찍는 것도 조심스러워서 블로그 자체도 쉬게 되었다.

이러면 안되는데... 그래서 반성하고 최대한 하루에 하나씩 백준 문제풀이를 하고자 나만의 위클리 챌린지를 시작해보려고 한다..!

 

그런데 우선 첫 문제 골드부터 막혀서 너무 슬펐다.. 흑흑

내가 이렇게 멍청했나(멍청멍청)

 

가장 먼저 보자마자 다익스트라 알고리즘으로 풀어야한다는 생각이 들었으나 점점 문제를 풀면 풀수록 미궁으로 빠졌다. 왜냐하면 문제 성공의 기준은 최소의 비용을 들이는 것이 아니라 원장이 내는 비용이 최소여야한다로 조금씩 다르기 때문이다. 그래서 다익스트라 알고리즘을 변형해서 풀어야 한다.

 

하지만 하루 넘게 노려보아도 도저히 답을 알 길이 없어서 문제를 풀어내신 분의 알고리즘을 보고 풀었는데, 오히려 좋.아.

이를 통해 그동안 평소에 궁금했던 문제들에 대한 해답을 찾아낼 수 있었다.

 

1. 정형화된 알고리즘 문제가 아닌 것은 어떻게 접근하고 풀어야 할까?

2. 무한의 수는 어떻게 표현하는가(대답 잘 못한 면접 질문이었음)

 

위 내용은 차차 문제를 풀면서 알아가고, 결국 이 문제의 쟁점은 원장이 얼마를 내느냐이다.

그래서 원장이 내야하는 최소한의 가격을 알아내기 위해서는 결과적으로 이분 탐색을 쓰고, 알아내는 과정에는 다익스트라를 사용하는 것이 관건이다.

•  다익스트라 함수의 인자 :  문제가 요구하는 원장이 내야하는 비용 X원. 
• 다익스트라 함수의 반환값 : 사용되는 간선들은 X원 이하거나 X원보다 비싼 간선이 K개 이하이면 True 반환. 이 경우가 아니면 원장이 내야하는 비용이 X원보다 비싸므로 False 반환

다익스트라 함수의 인자를 정하기 위해 main함수에서 이진 탐색을 이용해 최소 가능 값을 찾아낸다. 평소 다익스트라를 이용해서 최소 간선 비용만 구하는 것과 다르다는 것이 이 문제의 매력 포인트다. 이렇게 다익스트라를 통해서 X원보다 비싼 간선의 개수만을 세는 방법은 간선의 cost를 직접 더한 후 비교한 것과 다르게 X원보다 비싸면 1로 세고, 안 비싸면 0으로 처리해버린다. 그러면 결국 간선 비용을 나타내는 dist배열에는 1부터 각 인덱스까지의 X원보다 비싼 간선의 개수가 기록된다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
int dist[1001];
vector<vector<pair<int,int>>> graph(1001);
int n, p, k;

bool pay(int price);

int main(void){
    int a, b, c;
    int ans = -1;
    cin >> n >> p >> k;
    for(int i = 0;i < p;i++){
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    int l = 0, r = 1e7;
    while(l <= r){
        // 연산 속도 향상
        int mid = (l + r) >> 1;
        // 이분 탐색으로 다익스트라
        if(pay(mid)){
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans;
}
// 주어진 비용 이하의 금액을 들여서 1번 컴퓨터와 N번 컴퓨터를 연결할 수 있는가
// 주어진 비용보다 비싼 간선을 선택하지 않거나, price 비용보다 비싼 간선은 k개 이하일 때 가능
// 주어진 비용보다 비싼 간선이 k개 이하인지 판단 결과 리턴
bool pay(int price){
    // min heap
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, 1});
    // 0x3f는 주로 무한을 표기하기 위해 자주 쓰인다.
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    while(!pq.empty()){
        int w = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        // 이미 더 짧은 경로로 갱신된 경우
        if (w > dist[now]) continue;
        for(int i = 0; i < graph[now].size();i++){
            // price 이하의 가중치를 가진 간선 0, price보다 비싼 가중치를 가진 간선은 1로 처리
            int w2 = w + (graph[now][i].second > price);
            int next = graph[now][i].first;
            if(w2 >= dist[next]) continue;
            dist[next] = w2;
            pq.push({w2, next});
        }
    }
    return dist[n] <= k;
}

위 코드를 보고 드는 사소하지만 중요한 의문! 💡

1. 왜 r을 1e7(=10^7)로 설정하였는가?

이분 탐색에서 r에는 최댓값을 입력하여야 한다. 문제를 보면 가격은 1이상 1,000,000라서 지수표기법을 이용해 1e7이라고 입력했다.

 

2. 왜 dist 배열을 0x3f로 초기화하는가?

나는 평소 무한을 표기하기 위해서는 해당 자료형의 모든 비트를 1로 처리하면(만약 signed 변수라면 MSB 비트 제외) 그게 최댓값인줄 알았다. 즉 만약 int형 변수에서 무한을 표기한다고 치면 32비트의 최댓값인 0x7fffffff라고 표기했다. 만약 일반적인 비교만 한다면 그렇게 사용해도 무방하지만, 최선은 아니다. 왜냐하면 대다수의 경우 일반적인 비교만 하지 않고 일정한 연산 후에 비교하는 편이기 때문이다.

예) if (D[u] + w[u][v] < D[v]) D[v] = D[u] + w[u][v]

이렇게 쓰이는 예에서 우리는 w[u][v] = INF를 통해 u와 v 사이에 간선이 없다는 사실을 파악 가능하다. 만약 INF를 0x7fffffff로 설정하면 D[u] + w[u][v]의 연산에서 overflow가 발생하고 음수가 되어버린다.

 

이러한 경우를 방지함과 동시에 무한을 표현하기 위해서 infinity + infinity is still infinity 라는 식을 세운다. 0x7fffffff은 이에 부합하지 않기에 0x3f3f3f3f를 infinity로 설정하는 것이 가장 Ingenious한 방법이다. 0x3f3f3f3f은 십진수로 1061109567로 10^9보다 살짝 큰 수이다. 대부분의 수는 10^9를 넘지 않으므로 대부분의 수보다 크다는 점에서 이보다 큰 수를 제외하면 0x3f3f3f3f은 infinity로 쓰일 수 있다.

0x3f3f3f3f은 infinity + infinity is still infinity도 성립하므로 무한임을 증명한다. 0x3f3f3f3f + 0x3f3f3f3f = 2122219134이다. 이는 32비트를 넘지 않아 overflow가 발생하지 않는다. 

마지막으로 우리가 평소 array를 memset으로 초기화할 때, 0x3f3f3f3f는 또다시 유용한 일을 해낸다. memset은 바이트단위로 메모리를 초기화하는데, 즉 4개의 비트씩 초기화한다. 0x3f3f3f3f의 경우 0x3f라는 바이트(4비트)가 반복되는 양상을 띄기 때문에 초기화 가능하다. 

 

 

참고

- How to convert 0x3f to decimal?

- memset은 어떤 수로만 초기화될까

- https://topic.alibabacloud.com/a/use-0x3f3f3f-to-represent-infinity_8_8_10254941.html