글 읽기 - 반례를 못찾겠습니다

mjun09 4년 전 0

반례가 떠오르질않네요...

도와주세요 ㅠㅠ

#include <iostream>

using namespace std;

struct graph{
	int v1, v2, cost;
};

int N, M, K;
bool check;
int parent[1001];
int chk[1001];
struct graph g[600000];

int find(int vertex) {
	// 부모노드를 찾으면 반환
	if (vertex == parent[vertex])
		return vertex;

	// 찾지못했으면 현재 노드의 부모노드를 따라 이동
	return parent[vertex] = find(parent[vertex]);
}

void merge(int v1, int v2) {
	check = false;

	v1 = find(v1);
	v2 = find(v2);

	// 루트노드가 같으면(싸이클을 형성하면) check : false
	if (v1 == v2)
		return;
	// 싸이클을 형성하지 않으면 합병, check : true
	else if (v1 > v2) {
		parent[v1] = v2;
	}
	else {
		parent[v2] = v1;
	}
	check = true;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int start = 1;
	cin >> N >> M >> K;

	// 그래프 입력받기
	for (int i = 1; i < M + 1; i++) {
		cin >> g[i].v1 >> g[i].v2;
		g[i].cost = i;
	}


	while (K) {
		int cnt = 1;
		int result = 0;

		// 각 노드의 부모노드 초기화
		for (int i = 1; i < N + 1; i++) {
			parent[i] = i;
			chk[i] = 0;
		}

		// MST
		for (int i = start; i < M + 1; i++) {
			merge(g[i].v1, g[i].v2);

			if (check == true) {
				if (chk[g[i].v1] == 0 && chk[g[i].v2] == 0) {
					chk[g[i].v1] = cnt;
					chk[g[i].v2] = cnt++;
				}
				else if (chk[g[i].v1] == 0) {
					chk[g[i].v1] = chk[g[i].v2];
				}
				else if (chk[g[i].v2] == 0) {
					chk[g[i].v2] = chk[g[i].v1];
				}
				else {
					if (chk[g[i].v1] < chk[g[i].v2])
						chk[g[i].v2] = chk[g[i].v1];
					else
						chk[g[i].v1] = chk[g[i].v2];
				}

				result += g[i].cost;
			}
		}

		for (int i = 1; i < N; i++) {
			if (chk[i] != chk[i + 1]) {
				result = 0;
				break;
			}
		}

		// 결과 출력
		if (result == 0) {
			while (K) {
				cout << 0 << " ";
				K--;
			}
			return 0;
		}
		else
			cout << result << " ";
		K--;
		start++;
	}
}

pichulia 4년 전 1

95번째 줄에서 chk[i] == chk[i+1]을 하는게 맞나요?

열심히 merge를 해놓고 이 정보를 전혀 활용하지 못하고 있습니다

mjun09 4년 전 0

chk배열로 같은 그래프에 속하는지 여부를 판단하려고 하였습니다!

따라서 chk 배열이 모두 같은값을 가진다면 하나의 그래프가 완성되어 MST가 완성되는 것으로 판단하였고

chk 배열안에서 단 하나라도 다른 값을 가진다면 두 개 이상의 그래프가 되므로 MST가 만들어질 수 없다고 판단하였는데..

혹시 제 생각 중 어느 부분에서 미스가 난건지 좀더 상세히 알려주실수있으신가요? ㅠㅠ

pichulia 4년 전 2

chk값이 제대로 갱신이 안될것입니다.

chk값이 1인 노드가 5개 있고

2인 노드가 5개 있는데

이 둘을 연결하는 간선이 추가됐으면

chk가 2인 노드들이 '전부' 1로 바뀌는 것을 의도하신거같은데

실제 동작은 그렇지 않을 것입니다...

폰이라서 직접 돌려보지는 못해서 예제는 확인을 못하겠습니다만..

아마 아래의 데이터의 경우 맛이 가지 않을까 싶습니다.

mjun09 4년 전 0

아 세상에.... 정말 멍청했네요.. ㅠㅠ 감사합니다 덕분에 잘 해결했습니다!

말씀해주신 반례를 해결하도록해서 맞았습니다!

추가적으로 맨처음에 말씀해주신걸 토대로 생각해보니 find 함수를 사용하면 될것같더군요!

멍청하게 parent 배열로 비교하다가 안되는거같아 새로 배열을 만들었었는데.. 감사합니다 :D

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

문제

문제

출처

ICPC

반례를 못찾겠습니다

mjun09 4년 전 0

pichulia 4년 전 1

mjun09 4년 전 0

pichulia 4년 전 2

mjun09 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말