백준 1922 네트워크 연결

그래프 문제는 이번 기회로 처음 풀어보아 성취감이 생겼습니다. 이번 문제에서는 Edge(점을 연결한 선)들을 값을 기준으로 오름차순으로 정렬해준 뒤, 순서대로 사용하면 비용이 최소가 되어 해결이 되는 문제였습니다. 2차원 배열이던, 구조체 또는 객체를 이용하여 Edge의 정보를 입력받을 수 있게합니다. (a점, b점, 가중치) 그 뒤 가중치 기준으로 정렬을 합니다. 그 뒤 정렬 된 순서대로 연결을 시도합니다. 연결을 어떻게 저장하고 그래프가 순환되는지 판단하는지 중요한 것 같은데 저는 1차원 배열과 재귀를 이용하여 연결된 점들이 단 하나의 점을 가르키게 해주었습니다. 이 방법은 입력 값 set이 주어진 순서(a1, b1, val1), (a2, b2, val2) 식의 순서라던가 입력 값 set의 구성순서 (a, b, val) (b, a, val) 에 배열이 각기 다르게 표현되는 식의 영향을 받지만, 연결된 점들 모두는 결국 연결된 점들중에 임의의 하나의 점을 가리키게합니다. 즉, 같은 연결된 그룹의 점이라면 모든 점들은 하나의 점의 값을 갖습니다. 결국에 이 방법으로, 입력받은 임의의 Edge를 통해 두 점이 주어졌을 때 두 점이 값이 다르다면 연결이 되고, 값이 같다면 같은 그룹내에 있는 점이라는 것이라 판단하여 연결하지 않습니다. 따라서 최소 비용 그래프 문제를 풀 수 있었습니다.

#include <stdio.h>

#include <stdlib.h>

typedef struct {

int a, b, w;

}Edge;

Edge e[100001];

int rep[1001];

int mycmp(const void* a, const void *b){

const Edge *sa = (const Edge*)a;

const Edge *sb = (const Edge*)b;

return sa->w-sb->w;

}

int find(int x){

if (x==rep[x]) return x;

else return (rep[x] = find(rep[x]));

};

int main(){

int n, m;

scanf("%d %d", &n, &m);

for (int i=0; i<m ; i++) 

scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].w);

for(int i=0; i<=n; i++) rep[i]=i;

qsort(e, m, sizeof(Edge), mycmp); 

int cnt=0, ans=0;

for (int i=0; i< m && cnt<n; i++, n++){

int r1 = find(e[i].a), r2 = find(e[i].b);

if (r1==r2) continue;

rep[r1]=r2;

ans+=e[i].w;

}

printf("%d\n", ans);

return 0;

}

제 소스코드는 일부 백준사이트의 타 상위권 유저들의 영향을 받았거나 백준님 강의를 통해 배웠으므로로 유사한점이 많습니다. 또는, 당연한 알고리즘의 사용 이라던가.... 등등.. 참고하여 주의있게 사용해주시길 바랍니다.