[C] 백준 - 1043번: 거짓말

11월 21일(화) - 자료 구조 (1043번)

1043번: 거짓말

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전

int main(void)
{
	...

	if (num_truth == 0)
	{
		printf("%d", 0);
		return 0;
	}
	else
	{
		for (int i = 0; i < M; i++)
		{
			for (int j = 2; j <= party[i][0]; j++)
			{
				Union(party[i][1], party[i][j]);
			}
		}

		for (int i = 0; i < M; i++)
		{
			for (int j = 1; j <= party[i][0]; j++)
			{
				if (find(party[i][j]))
				{
					continue;
				}
				else if (j == party[i][0])
				{
					count++;
				}
			}
		}
	}

	printf("%d", M - count);
	return 0;
}

// 수정 후

int main(void)
{
	...
    
	for (int i = 0; i < M; i++)
	{
		for (int j = 2; j <= party[i][0]; j++)
		{
			Union(party[i][1], party[i][j]);
		}
	}
	for (int i = 0; i < M; i++)
	{
		for (int j = 1; j <= party[i][0]; j++)
		{
			if (find(party[i][j]) == 0)
			{
				break;
			}
			else if (j == party[i][0])
			{
				count++;
			}
		}
	}

	printf("%d", count);
	return 0;
}

1. if (진실을 아는 사람의 수가 0명인 경우 먼저 0을 출력하고 종료) - else 형태로 크게 생각

-> else 안에서 꼬임

-> if - else 구조 삭제하고, 그냥 M개의 for문 돌리면서 Union함수 실행과 find함수를 통해서 파티의 개수 출력

 

2. find함수를 통해서 return하는 그룹번호가 0이 아닌 경우에 continue를 하고, 0이 들어간 경우에 변수 count++

최종적으로 (전체 파티의 개수) - (거짓말이 불가능한 파티의 개수), 즉 M - count를 출력하려했음

-> return하는 그룹번호가 0이면 break 걸고, break가 걸리지 않은 경우에만 변수 count++

-> 최종적으로 count를 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int parent[51];
int party[51][51];
int count = 0;

int find(int x)
{
	if (parent[x] == x)
	{
		return x;
	}

	return parent[x] = find(parent[x]);
}

void Union(int x, int y)
{
	x = find(x);
	y = find(y);

	if (x != y)
	{
		if (x < y)
		{
			parent[y] = x;
		}
		else
		{
			parent[x] = y;
		}
	}
}

int main(void)
{
	// 첫째 줄 -> 사람의 수 N, 파티의 수 M 입력 + N개 만큼의 그룹번호 생성
	int N, M;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
	{
		parent[i] = i; // N개 만큼의 그룹번호 생성
	}


	// 둘째 줄 -> 진실을 아는 사람의 수와 번호 입력 + 진실을 아는 사람의 그룹번호는 0으로 통일
	int num_truth;
	scanf("%d", &num_truth);

	int who_know_truth;
	for (int i = 0; i < num_truth; i++)
	{
		scanf("%d", &who_know_truth);
		parent[who_know_truth] = 0; // "진실을 아는 사람의 그룹번호는 0으로 통일"
	}
	

	// 셋째 줄부터 -> M개의 줄에서 각각의 파티마다 오는 사람의 수와 번호를, 2차원 배열인 party[i][0] 와 party[i][ ]에 입력
	for (int i = 0; i < M; i++)
	{
		scanf("%d", &party[i][0]);
		for (int j = 1; j <= party[i][0]; j++)
		{
			scanf("%d", &party[i][j]);
		}
	}


	// 각각의 파티마다 사람의 수가 party[i][0]에 저장되어있기 때문에, party[i][1]부터 party[i][j]까지 그룹을 합쳐주는 Union함수를 실행
	for (int i = 0; i < M; i++)
	{
		for (int j = 2; j <= party[i][0]; j++)
		{
			Union(party[i][1], party[i][j]);
		}
	}
	for (int i = 0; i < M; i++)
	{
		for (int j = 1; j <= party[i][0]; j++)
		{
			if (find(party[i][j]) == 0) // return하는 그룹번호가 0이다 -> 파티에 진실을 아는 사람이 최소 1명 존재한다 -> 거짓말을 못하는 파티
			{
				break;
			}
			else if (j == party[i][0]) // if에서 break가 안걸렸다 -> return하는 그룹번호 중 0이 없다 -> 파티에 진실을 아는 사람이 아무도 없다 -> 거짓말을 해도 괜찮은 파티
			{
				count++; // 거짓말이 가능한 파티의 개수++
			}
		}
	}

	printf("%d", count); // 최종적으로 거짓말이 가능한 파티의 개수 출력
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ