글 읽기 - union find 다른 논리인가요?

jangzzang 4년 전 0

첫번째 풀이는 wa인데 prev배열에 -cost를 각각 지정합니다. 즉, 1번 tc의 경우 -10 -10 -20 -20 -30으로 지정했구요.

입력을 받으면서 merge 시키는데 만약 루트노드가 다른경우 prev의 값이 최대인 루트로 merge 시킵니다. 그렇게 다 merge 시키고

for문을 돌면서 모든 노드의 ROOT를 확인해서 ROOT가 CHECK가 안됐을 경우 그 root의 abs(prev)값이 지출 비용이 됩니다. 이런 식으로 확인했고

2번은 prev를 -1로 다 초기화한 후 prev가 -1인 노드만 확인했습니다.

즉 큰 차이는 비용을 prev에 들고 다니느냐, 비용을 배열에 저장 해 놓느냐인데 1번이 어디서 안되는건지 잘 모르겠습니다 ㅠㅠ

1번 코드 WA
#include<iostream>
#include<cstring>

int n, m, k;
int pay[11000];

void merge(int x, int y);
int find(int x);
int prev[10010];
bool check[10010];
int max(int a, int b) { if (a >= b)return a; else return b; };
int main() {

	scanf("%d %d %d", &n, &m, &k);
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &pay[i]);
		prev[i] = -pay[i];
	}

	for (int i = 1; i <= m; i++) {
		int v, w;
		scanf("%d %d", &v, &w);
		merge(v, w);
	}
	int ans = 0;
	//모든 학생을 친구로 만들 수 있을까
	for (int i = 1; i <= n; i++) {
		int t = find(i);
		if (!check[t]) {
			k += prev[t];
			ans += -prev[t];
			check[t] = true;
		}
	}
	if (k < 0) {
		printf("Oh no");
	}
	else {
		printf("%d", ans);
	}

}


int find(int x) {
	if (prev[x] < 0)return x;
	prev[x] = find(prev[x]);
	return prev[x];
}

void merge(int x, int y) {
	int xRoot = find(x);
	int yRoot = find(y);
	if (xRoot == yRoot)return;
	//큰거를 왼쪽에 두고 작은수를 오른쪽에서 왼쪽으로 붙이자.
	int rootValue = max(prev[xRoot], prev[yRoot]);
	if (prev[xRoot] >= prev[yRoot]) {
		//x가 더 클경우 y를 x에 단다
		prev[xRoot] = rootValue;
		prev[y] = xRoot;
	}
	else {
		//y가 클경우 x를 y에 단다
		prev[yRoot] = rootValue;
		prev[x] = yRoot;
	}

}


///////2번 AC
#include<iostream>
#include<cstring>

int n, m, k;
void merge(int x, int y);
int find(int x);
int prev[10010];
int cost[10010];
int max(int a, int b) { if (a >= b)return a; else return b; };
int main() {
	memset(prev, -1, sizeof(prev));
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cost[i]);
	}

	for (int i = 1; i <= m; i++) {
		int v, w;
		scanf("%d %d", &v, &w);
		merge(v, w);
	}
	int ans = 0;
	//모든 학생을 친구로 만들 수 있을까
	for (int i = 1; i <= n; i++) {
		if (prev[i] == -1) {
			ans += cost[i];
		}
	}
	if (k<ans) {
		printf("Oh no");
	}
	else {
		printf("%d", ans);
	}

}


int find(int x) {
	if (prev[x] < 0)return x;
	prev[x] = find(prev[x]);
	return prev[x];
}

void merge(int x, int y) {
	int xRoot = find(x);
	int yRoot = find(y);
	if (xRoot == yRoot)return;
	if (cost[xRoot] > cost[yRoot]) {
		prev[xRoot] = yRoot;
	}
	else {
		prev[yRoot] = xRoot;	
	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

union find 다른 논리인가요?

jangzzang 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말