c언어 23034번 조별과제 멈춰! (백준)

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{int x, y, v;}Node; //간선 구조체
typedef struct Pair{int y, v;}Pair; //정수형 변수 두개 묶어논 구조체
typedef struct qNode { //큐에 들어갈 구조체
	Pair data;
	struct qNode* next; //다음 큐의 구조체를 가리킵니다.
}qNode;

typedef struct Queue {//큐
	qNode* front;
	qNode* rear;
	int cnt;
}Queue;

void init(Queue* q) {//큐 초기화
	q->cnt = 0;
	q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {return q->cnt==0;} //큐가 비었는가?

void push(Queue* q, Pair e) { //큐에 집어넣기
	qNode* newNode = (qNode*) malloc(sizeof(qNode));
	newNode->next = NULL;
	newNode->data.y = e.y;
	newNode->data.v = e.v;
	
	if(isEmpty(q)) q->front = newNode;
	else q->rear->next = newNode;
	q->rear = newNode;
	q->cnt++;
}

Pair pop(Queue* q) { //큐에서 꺼내기
	Pair e;
	qNode* ptr;
	
	ptr = q->front;
	e.y = ptr->data.y;
	e.v = ptr->data.v;
	q->front = ptr->next;
	free(ptr);
	q->cnt--;
	
	return e;
}

Pair peek(Queue* q) {return q->front->data;} //큐에서 가장 앞에있는 것을 반환하기

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 p[n+1];
	int cnt[n+1];
	Node g[m], key;
	Pair line[n+1][n-1];
	for(i=1; i<=n; i++) { //배열 초기화
		p[i] = i;
		cnt[i] = 0;
	}
	
	for(i=0; i<m; i++) scanf("%d %d %d", &g[i].x, &g[i].y, &g[i].v); //간선 입력받음
	
	gap = m/2;
	while(1) {                     //간선들을 가중치를 기준으로 오름차순 정렬
		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 mst = 0;
	for(i = 0; i<m; i++) {            //krustal 알고리즘
		if(find(p, g[i].x) != find(p, g[i].y)) {
			mst += g[i].v;
			Pair tmpx = {g[i].y, g[i].v};
			Pair tmpy = {g[i].x, g[i].v};
			line[g[i].x][cnt[g[i].x]++] = tmpx;
			line[g[i].y][cnt[g[i].y]++] = tmpy;
			merge(p, g[i].x, g[i].y);
		}
	}
	
	Queue q; //큐 생성
	init(&q); //큐 초기화
	int Q; //몇개의 질문?
	scanf("%d", &Q);
	
	for(i=0; i<Q; i++) {               //큐를 이용한 BFS
		int x, y, max=0, sw=0;
		scanf("%d %d", &x, &y);
		Pair pairTmp = {x, 0};
		char visited[1001] = {};
		
		push(&q, pairTmp);
		while(!isEmpty(&q)) {
			Pair left = peek(&q);
			
			for(j=0; j<cnt[left.y]; j++) {
				if(sw) break;
				
				int right = line[left.y][j].y;
		
				if(!visited[right]) {
					pairTmp = left;
					left.v = (left.v > line[left.y][j].v) ? left.v : line[left.y][j].v;
					
					if(right == y) {
						sw=1;
						max = left.v;
						break;
					}
					
					left.y = right;
					push(&q, left);	
					left = pairTmp;				
				}
			} 
			visited[pop(&q).y] = 1;
		}
		printf("%d\n", mst-max);
	}
}

 

풀이 : krustal 알고리즘으로 mst의 가중치를 구한다음

 입력받은 x에서 y로 갈 때의 경로 중 가장 가중치가 큰 곳을 bfs (또는 dfs)로 찾은다음 mst의 가중치에 그 값을 뺀 후 출력하면 됩니다.

 

0. 구조체 만들기 : 저는 간선을 담을 구조체와, 정수형 변수 두개를 묶어놓을 구조체 두개를 만들었습니다.

1. 가변적인 큐와 함수들 만들기, 큐를 동적할당을 이용하여 구현했습니다.

2. n, m입력받기

3. 간선들 입력받기

4. 간선들을 가중치를 기준으로 오름차순 정렬

5. krustal 알고리즘으로, mst의 가중치를 구하며, 이 과정에서, mst에선 각 노드들이 어떻게 연결되어있는지를 따로 배열을 만들어서 저장한다.

6. x, y을 입력받을 때 마다 5.에서 만든 배열을 이용하여, mst에서 x->y로 갈 때 가장 가중치가 큰 간선을 dfs 또는 bfs으로 찾습니다. 그런다음 mst의 가중치에서 탐색으로 찾은 가장 큰 가중치를 뺀 것을 출력하면 됩니다.

 

주의 : 저같은 코린이들은 그냥 c++로 푸는게 더욱 효율적입니다.

 

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

23034번: 조별과제 멈춰!