글 읽기 - 3% 입구 컷 당하네요 ㅠㅠ (주석있음, 발상 설명있음, 예제 다 통과)

shwjdgh3842 2년 전 1

발상은 다음과 같습니다.

우선 진실을 알고 있는 사람을 벡터에 저장한 다음 원소들을 모두 marge합니다. (이때 기준을 0으로 해서 0과 루트가 같으면 진실을 알고있다고 판단할 수 있습니다.)

파티에 참여하는 사람 중 진실을 아는 사람이 있다면 그 파티 참여인원 모두를 0과 marge합니다.

그리고 진실을 말할 수 있는 파티인지 탐색하여 답을 도출합니다.

로직이 잘못된걸까요? 아님 구현에서 미스가 있는걸까요

68~74 주석을 해제하면 해결되는데 도대체 어떤 반례때문에 주석문이 추가되어야하는지 모르겠습니다

도움 부탁드립니다 ㅠ

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
int n, m;
int parent[51], level[51];
bool ly[50];
vector<int>v2[50];
//u의 꼭대기를 반환
int find(int u) {
	if (u == parent[u]) {
		return u;
	}
	return parent[u] = find(parent[u]);
}
//u와 v에 해당하는 트리를 합침
void marge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) {
		return;
	}
	if (level[u] > level[v]) {
		//u와 v를 바꿈
		int im = u, u = v, v = im;
	}
	parent[u] = v;
	if (level[u] == level[v]) {
		level[v]++;
	}
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		parent[i] = i;
	}

	//진실을 아는 사람들을 v에 넣음
	vector<int>v;
	int num1;
	cin >> num1;
	for (int i = 0; i < num1; i++) {
		if (num1 == 0) break;
		int a;
		cin >> a;
		v.push_back(a);
	}
	
	//파티에 참여하는 사람들을 파티열별로 v2에 넣음
	
	for (int i = 0; i < m; i++) {
		int num2;
		cin >> num2;
		for (int j = 0; j < num2; j++) {
			int a;
			cin >> a;
			v2[i].push_back(a);
		}
	}
	//각 파티에 참석하는 사람들을 트리로 묶는다.
	/*for (int i = 0; i < m; i++) {
		if (v2[i].size() >= 2) {
			for (int j = 0; j < v2[i].size() - 1; j++) {
				marge(v2[i][j], v2[i][j + 1]);
			}
		}
	}*/
	if (num1 == 0) {
		cout << m;
		return 0;
	}
	//v에 저장된 진실을 아는 사람들을 0과 같은 트리로 묶는다
	for (int i = 0; i < v.size(); i++) {
		marge(v[i], 0);
	}
	//파티에 참석하는 사람 중 진실을 아는 사람이 있는 파티인 경우 모두를 묶는다
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < v2[i].size(); j++) {
			if (find(0) == find(v2[i][j])) {
				//i번째 파티에서는 진실을 언급해야한다.
				ly[i] = true;
				//i번째 파티내 파티원 전체를 트리로 묶는다
				for (int k = 0; k < v2[i].size(); k++) {
					marge(v2[i][k], 0);
				}
				break;
			}
		}
	}
	//뒤에서 새롭게 묶인 사람이 잇을 수 있으므로 한번 더 돌아야한다.
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < v2[i].size(); j++) {
			if (find(0) == find(v2[i][j])) {
				//i번째 파티에서는 진실을 언급해야한다.
				ly[i] = true;
				break;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		if (ly[i] == false) {
			ans++;
		}
	}
	cout << ans;
}

recoma 2년 전 24

98 라인에서 새롭게 묶인 사람이 있어, 한번 더 돌아도, 다시 새롭게 묶인 사람이 존재합니다. 새롭게 묶였음에도 불구하고 체크를 못했기 때문에 오답을 출력합니다.

68 ~ 74 라인에서는 이러한 경우를 미리 처리를 해 두었기 때문에 정답 처리가 될 수 있었습니다.

반례를 예로 들면 [1,2,3], [4,5,6], [6,7,8], [3,8] 이 있고, 진실을 아는 사람이 [1] 일 때 84 라인을 작동시키면 [1,2,3]과 [3,8]이 묶이게 되어 [1,2,3,8], [4,5,6], [6,7,8]이 됩니다. 그리고 98라인에 의해 [1,2,3,8]과 [6,7,8]에 [8]이 공통으로 포함되어 있으므로 [1,2,3,6,7,8], [4,5,6]이 됩니다. 따라서 주석 처리할 경우에 대한 출력은 [4,5,6]으로 1이 되지만. 나머지 두 집합에는 [6]이 공통으로 들어가 있기 때문에([1,2,3,4,5,6,7,8]), 6도 진실을 알게 되므로, 실제 정답은 0이 됩니다.

반면, 68 ~ 74 라인을 주석 해제하게 되면 같은 파티원 끼리 한 집합으로 묶이게 되는데, 이 과정에서 모든 파티([1,2,3], [4,5,6], [6,7,8], [3,8])들이 하나로 묶여, 84라인으로 본 작업을 시작했을 때 이미 [1,2,3,4,5,6,7,8]로 전부 묶여 있으므로 0을 출력하게 됩니다.

input:
8 4
1 1
3 1 2 3
3 4 5 6
3 6 7 8
2 3 8

answer:
0

output:
1

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

문제

문제

출처

ICPC

3% 입구 컷 당하네요 ㅠㅠ (주석있음, 발상 설명있음, 예제 다 통과)

shwjdgh3842 2년 전 1

recoma 2년 전 24

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말