글 읽기 - Union-find 방식으로 짜봤을 때 틀리는 이유가 뭘까요?

eastern7star 5년 전 0

질문 읽어주셔서 감사합니다 ㅎ

Disjoint set (Union-find) 방식을 이용하여 O(KlogK) 시간에 풀어보려고 했는데

여러 가지 테스트 케이스로 테스트 해봤을 경우 맞았으나, 틀렸다고 뜨네요.

혹시 어떤 경우에 틀린건지, 틀린 부분은 어딘지 알려주실분 계신가요??

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define _x first
#define pos first
#define id second
#define _y second

void mergeBlocks(vector<int>& parent, vector<pair<pair<int, int>, int>>& b) {
	for (int k = 0; k < b.size() - 1; k++) {
		if (abs(b[k].pos._x - b[k + 1].pos._x) + abs(b[k].pos._y - b[k + 1].pos._y) <= 1)
			parent[b[k + 1].id] = b[k].id;
	}
}

int main() {
	int T, M, N, K, i, c;
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		scanf("%d %d %d", &M, &N, &K);
		vector<pair<pair<int, int>, int>> bx(K), by(K);
		vector<int> p(K);
		for (int k = 0; k < K; k++) {
			scanf("%d %d", &(bx[k].pos._x), &(bx[k].pos._y));
			by[k].pos._x = bx[k].pos._y;
			by[k].pos._y = bx[k].pos._x;
			bx[k].id = by[k].id = p[k] = k;
		}
		sort(bx.begin(), bx.end());
		sort(by.begin(), by.end());
		mergeBlocks(p, bx);
		mergeBlocks(p, by);
		for (i = 0, c = 0; i < p.size(); i++) if (p[i] == i) c++;
		printf("%d\n", c);
	}

	return 0;
}

njw1204 5년 전 1

유니온 파인드가 잘못됐습니다

eastern7star 5년 전 1

njw1204님 감사합니다 ㅎㅎ find 하는 부분 생각없이 생략을 너무 많이 했네요 ㅠ

덕분에 문제 해결했습니다! ㅎㅎ

int find(int idx, vector<int>& parent) {
	if (parent[idx] == idx) return idx;
	else return(parent[idx] = find(parent[idx], parent));
}

void mergeBlocks(vector<int>& parent, vector<pair<pair<int, int>, int>>& b) {
	for (int k = 0; k < b.size() - 1; k++) {
		if (abs(b[k].pos._x - b[k + 1].pos._x) + abs(b[k].pos._y - b[k + 1].pos._y) <= 1)
			parent[find(b[k].id, parent)] = find(b[k + 1].id, parent);
	}
}

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

문제

문제

출처

ICPC

Union-find 방식으로 짜봤을 때 틀리는 이유가 뭘까요?

eastern7star 5년 전 0

njw1204 5년 전 1

eastern7star 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말