글 읽기 - 유니온파인드 사용, 채점시작하자마자 틀림

onaeonae1 5년 전 0

친구들의 연결관계를 유니온 파인드를 통해 서로소 집합을 찾고

해당 집합 내에서의 비용 최솟값을 찾아서 check 배열의 루트 노드 인덱스, 즉 check[parents[i]]를 갱신시켜 주었습니다.

그리고 이후 N만큼 반복문을 돌려서 check[i]가 INF가 아닌 경우, 즉 같은 집합(같은 루트 노드)내에서의 최솟값으로 갱신된 경우에 sum에 값을 추가해주었습니다.

그런데 채점을 하자마자 틀리는데 어떤 부분에서 문제가 있을까요.. 알려주시면 감사하겠습니다.

#include<stdio.h>
#define lim 10005
#define INF 10000005
int getParent(int parent[], int x) //루트 노드 찾는 재귀함수
{
	if (parent[x] == x)
	{
		return x;
	}
	else
	{
		parent[x] = getParent(parent, parent[x]); 
	}
}
void unionParent(int parent[], int a, int b) //노드끼리 합쳐주고 가장 최소의 가격을 가져옴.
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b)
	{
		parent[b] = a;
	}
	else if(a>=b)
	{
		parent[a] = b;
	}
}
int findParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
int main()
{
	int N, M, K;; //사람수, 관계의 수, 소지금
	int parents[lim] = { 0, };  //연결 관계 표시를 위함
	int costs[lim] = { 0, };
	int check[lim] = { 0, };
	int sum = 0;
	scanf("%d %d %d", &N, &M, &K);
	
	for (int i = 1; i <= N; i++) //사람의 수 만큼
	{
		parents[i] = i; //각자의 루트노드는 각자로 초기화 해줌.
		scanf("%d", &costs[i]); //비용을 입력받고
		check[i] = INF;
	}
	for (int i = 1; i <= M; i++) //서로의 관계 설정
	{
		int u, v;
		scanf("%d %d", &u, &v);
		unionParent(parents, u, v); //서로를 합침.
	}

	for (int i = 1; i <= N; i++) //해당 루트 내에서의 최솟값 탐색 과정
	{
		if (check[parents[i]] >= costs[i])
		{
			check[parents[i]] = costs[i];
		}
	}
	for (int i = 1; i <= N; i++)
	{
		if (check[i] != INF)  //한번이라도 이 값이 바뀌었다면
		{
			sum += check[i]; 
		}
	}
	if (sum > K) //친구비 총합이 내 돈보다 많을 때
	{
		printf("Oh no");
	}
	else
	{
		printf("%d", sum);
	}
	return 0;
}

iron1209 5년 전 2

여기서 parents[i]는 꼭 최종 루트번호가 지정되는건 아닙니다. 그래서 getParents라는 함수를 따로 둬서 진짜 루트번호를 알아내려고 하는것이죠.

	for (int i = 1; i <= N; i++) //해당 루트 내에서의 최솟값 탐색 과정
	{
		if (check[parents[i]] >= costs[i])
		{
			check[parents[i]] = costs[i];
		}
	}
//를
for (int i = 1; i <= N; i++) //해당 루트 내에서의 최솟값 탐색 과정
	{
		if (check[getParent(parents, i)] >= costs[i])
		{
			check[getParent(parents, i)] = costs[i];
		}
	}
//로 바꾸시면 됩니다

iron1209 5년 전 0

그리고 getParents에 return을 안붙였네요

int getParent(int parent[], int x) //루트 노드 찾는 재귀함수
{
	if (parent[x] == x)
	{
		return x;
	}
	else
	{
		return parent[x] = getParent(parent, parent[x]);
	}
}

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

문제

문제

출처

ICPC

유니온파인드 사용, 채점시작하자마자 틀림

onaeonae1 5년 전 0

iron1209 5년 전 2

iron1209 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말