[BOJ] 11404 플로이드_Binary Search

플로이드

link

내 풀이

• 방식 : 플로이드 와샬
• 모든 정점에서 모든 정점으로 가는 최단 거리를 모두 구하는 알고리즘
• site A에서 site B로 갈때의 최소거리를 업데이트하기 위해 중간 node를 활용
• 하나의 노드를 중간 노드로 생각하고, 그 노드를 거쳐 갔을때 노드 사이의 거리값이 최소되도록 노드를 전체 탐색하여 Update
• 모든 노드(N)에 대해서 전체를 Update(N^2)하기 때문에 O(N^3) 시간 복잡도가 생김

📰code(python)

N = int(input())
num_bus = int(input())
bus = []
for _ in range(num_bus):
    a,b,p = list(map(int,input().split()))
    bus.append([a-1,b-1,p])
    
dp = [[int(1e9)]*N for _ in range(N)]

for a,b,p in bus:
    dp[a][b]=min(p,dp[a][b])
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i==j: dp[i][j] = 0
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])

for i in range(N):
    for j in range(N):
        if dp[i][j] == int(1e9): print(0, end = ' ')
        else : print(dp[i][j], end = ' ')
    print()

📰code(C++)

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

int n, c, arr[200002];
int val,p;

inline int router(int mid){
    val = arr[0]+mid;
    p = c-1;
    for(int i=1;i<n;i++){
        if (arr[i]>=val){
            p--;
            val = arr[i]+mid;
            if (p==0) return 1;
        }
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> c;
    for(int i = 0; i<n; i++)
        cin >> arr[i];
    
    sort(arr,arr+n);
    
    int left = 1, right = (arr[n-1]-arr[0])/(c-1)+1;
    int mid,answer;
    answer = 1;
    while (left<right){
        mid = (left+right)/2;
        if (router(mid)==1){
            answer=mid;
            left = mid+1;
        }
        else right = mid;
    }
    cout<<answer;
}

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡