[백준]핑크 플로이드(6091)

문제 링크 : [백준]핑크 플로이드(6091)

6091번: 핑크 플로이드

 

문제 설명

N개의 노드간의 최단거리가 인접행렬로 주어 질 때, 인접 리스트로 변형하여 출력하세요.

입력

N(노드의 갯수, 1 <= N <= 1,024)

V_ij(i에서 j까지의 최단거리)

5
5 14 3 7
13 2 6
11 7
4

 

출력

1 4
1 4
1 5
3 1 2 5
2 3 4

 

카테고리

#MST #크루스칼

 

시간 복잡도 상한

O(N²logN)

 

해결 방법

1. 모든 간선 중 비용이 가장 작은 간선은 항상 두 노드를 직접 잇는 간선이 됩니다.
2. 그렇게 찾은 간선을 간선 리스트에 저장합니다.
3. 1번에서 선택한 간선을 제외하고 나머지 간선 들 중 가장 작은 간선을 살펴봅니다.
4. 이때 그 간선의 양 끝 노드가 이미 더 작은 비용 간선들로 이어져있다면, 그 간선은 플로이드 와샬 알고리즘에 의해 만들어진 중간 지점을 경로하는 간선이 됩니다.
5. 1~4까지의 과정을 보면 크루스칼과 동일함을 알 수 있습니다.
6. 즉 플로이드 와샬 알고리즘을 돌리면서, Disjoint Set에서 두 노드가 같은 그룹에 있다면 continue, 그렇지 않다면 인접리스트에 정보를 저장하면 됩니다.

시간복잡도

O(N²logN²)

코드

#include<iostream>
#include<algorithm>
#include<vector>
#define F second.first
#define S second.second
#define N 1025
using namespace std;
typedef pair<int,pair<int,int>>P;
int n,i,j,c,g[N];
vector<P>v;
vector<int>a[N];
int f(int x){return x==g[x]?x:g[x]=f(g[x]);}
void u(int x,int y){g[f(x)]=f(y);}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)for(g[i]=i,j=i+1;j<=n;j++)cin>>c,v.push_back({c,{i,j}});
    sort(v.begin(),v.end());
    for(P x:v){
        if(f(x.S)!=f(x.F)){
            a[x.F].push_back(x.S);
            a[x.S].push_back(x.F);
            u(x.F,x.S);
        }
    }
    for(i=1;i<=n;i++){
        cout<<a[i].size();
        sort(a[i].begin(),a[i].end());
        for(int x:a[i])cout<<" "<<x;
        cout<<"\n";
    }
}