글 읽기 - C++] 맞은코드와 틀린코드의 차이를 모르겠습니다,

dlqudgus2587 4년 전 0

14행의 Union함수로 제출했을 때는 맞았고 25행의 union함수로 제출했을 때는 틀렸습니다가 나왔습니다.

테스트 케이스 잘 나오고 제가 만들어본 몇몇 예시들도 다 잘 나오는데 틀렸습니다가 나와서 구글링을 해봤더니 union함수에서 약간의 차이가 있어서 14행처럼 고쳤더니 맞았습니다.

제 생각에는, a(14행)나 ap(25행)나 둘 다 인자로 전달받은 a의 루트 노드 값을 저장하는 변수인데다가, 전달 인자가 reference가 아닌 단순 value이기 때문에 Union 함수 내에서 a의 값을 고쳐도 main에서는 어차피 변화하지 않을 것이라고 생각이 들어서, 전달인자 a의 값이 바뀌는 것도 아니고, 결국엔 둘 다 같은 함수인 것 같은데 왜 다른 결과가 나오는지 궁금합니다.

조언해주시면 감사하겠습니다.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;

int Find(int p[], int x) {
	if (p[x] == x) return x; 
	p[x] = Find(p, p[x]);
	return p[x];
}

//맞은 Union 함수
void Union(int p[], int a, int b) {
	a = Find(p, a);
	b = Find(p, b);
	if (a < b) {
		p[b] = a;
	}
	else
		p[a] = b;
}

//틀린 Union 함수
void Union(int p[], int a, int b) {
	int ap = Find(p, a);
	int bp = Find(p, b);
	if (ap < bp) {
		p[b] = ap;
	}
	else
		p[a] = bp;
}



int main() {
	int n, m, a,b,c;
	int* p;
	scanf("%d %d", &n, &m);
	p = new int[n + 1];

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

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		if (!a) {
			Union(p, b, c);
		}
		else {
			if (Find(p,b) == Find(p,c))
				printf("YES\n");
			else
				printf("NO\n");
		}
	}

	delete[] p;
}

p_ce1052 4년 전 3

맞은 코드를 보시면 인자로 넘겨받은 a,b,값 자체가 바뀌고 틀린 코드는 a,b값이 바뀌지 않았습니다. 루트를 찾지 못했죠. 그래서 틀린 union함수를 보시면 루트가 아닌 그냥 자기 부모를 저쪽 집합의 루트로 연결해버립니다. 그럼 자기 위의 부모들은 연결되지 않았죠. 그래서 틀립니다.

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

문제

문제

출처

ICPC

C++] 맞은코드와 틀린코드의 차이를 모르겠습니다,

dlqudgus2587 4년 전 0

p_ce1052 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말