c언어 13418번 학교 탐방하기 (백준)

#include <stdio.h>

typedef struct Node {int x,y,v}Node; //간선을 담을 구조체

int find(int p[], int x) { //노드가 속한 부분집합의 대표 노드 찾기
	if(x == p[x]) return x;
	return p[x] = find(p, p[x]);
}

void merge(int p[], int x, int y) {//두 노드가 속한 부분집합들 합치기
	x = find(p, x);
	y = find(p, y);
	if(x!=y) p[x] = y;
}

int main(void) {
	int n, m, i, j, gap;
	scanf("%d %d", &n, &m);
	int Up[n+1]; //최소 스패닝 트리를 위한을 위한 배열
	int Down[n+1]; //최대 스패닝(?) 트리를  위한 배열
	Node g[m+1]; //간선을 담을 배열
	Node key;
	
	for(int i=0; i<=n; i++) Up[i] = Down[i] = i; //초기화
	
	for(int i=0; i<=m; i++) {
		scanf("%d %d %d", &g[i].x, &g[i].y, &g[i].v); //간선 받기
	}
	
	gap = m/2;
	
	while(1) {                //shell sort
		if(gap%2==0) gap++;
		for(i=gap; i<=m; i++) {
			key = g[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.v < g[j].v) g[j+gap] = g[j];
				else break;
			}
			g[j+gap] = key;
		}
		if(gap == 1) break;
		gap >>= 1;
	}
	
	int upCnt = 0;
	int downCnt = 0;
	
	for(int i=0; i<=m; i++) {    //kurstal 알고리즘
		if(find(Up, g[i].x) != find(Up, g[i].y)) {
			if(!g[i].v) upCnt++;
			merge(Up, g[i].x, g[i].y);
		}
		if(find(Down, g[m-i].x) != find(Down, g[m-i].y)) {
			if(!g[m-i].v) downCnt++;
			merge(Down, g[m-i].x, g[m-i].y);
		}
	}
	
	printf("%d", upCnt*upCnt-downCnt*downCnt);
}

 

풀이 : krustal 알고리즘

 

1. n, m입력을 받습니다.

2. m+1개의 간선을 입력 받습니다.

3. 입력받은 간선을 가중치를 기준으로 오름차순 정렬합니다.

4. krustal알고리즘으로, 모든 학교를 탐방 할 때(트리)의 최소 가중치와, 최대 가중치를 구합니다.

중요한것은 간선의 정보가 0이면, 오르막길이며, 1이면 내려막길이다. 즉 0일 때 가중치를 1 증가시켜줍니다.

5. 피로도는 가중치의 제곱이며, 문제에선 최악일 때의 피로도에 최소 일 때의 피로도를 뺀 것을 출력해야 하므로,

최대 가중치 * 최대 가중치 - 최소 가중치 * 최소 가중치 를 출력하면 됩니다.

 

 

https://www.acmicpc.net/problem/13418

13418번: 학교 탐방하기