백준1043번 거짓말 C++로 구현해보기

---

```

백준1043번 거짓말 C++로 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 1043번 풀이

---

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

 

백준 1043번 거짓말은

난이도 중급 등급의 문제로서

 

글을 자세히 읽어봐야 하는 문제입니다.

 

허풍떨기 좋아하는 거짓말쟁이 Liar가 있습니다.

그는 파티에 참석하는데

 

법칙이 몇가지 있습니다.

 

1. 

파티 참석자 A가 진실을 알면 A가 참석한 모든 파티에 거짓말쟁이는 진실을 말해야 함

 

2.

파티 참석자 C가

진실을 모르지만

진실을 아는 사람과 같은 파티에 참석했다면

C가 참석한 다른 파티에서도

거짓말쟁이는 진실을 말해야 함

 

3.

파티 참석자 C가

진실을 모르는 상태에서 시작했더라도

2에 조건에 부합하면

재귀적으로 C와 같이 참석한 사람도

C와 같은 효과를 봄

 

법칙이 복잡합니다.

저는 문제를 잘못이해해서 한참 돌다가 풀었습니다.

잘 이해하셨다면

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

저는 클래스를 만들어서 풀었으며

 

입력속도를 줄여서 제한시간을 통과하기 위해서

string stream을 사용하였습니다.

 

		// 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용
		string inputStr;
		std::getline(cin, inputStr);
		stringstream ss(inputStr);
		ss >> TotalNumberOfPeople;
		ss >> TotalNumberOfParties;

 

string stream으로 값을 입력받고

 

 

파티 데이터라는 스트링 벡터를 만들어서

파티에 참석한 사람들 번호를 각 파티마다 저장하여서 사용하였고.

 

	vector<string> partyData;

 

party데이터에서 정보를 꺼내서

사람들과 연결된 관계를 2D 맵으로 표현했고

 

	// 사람과 사람이 맵핑된 2D 배열
	// 같이 파티에 간사람과 연결되 있으면 1 없으면 0
	int iArrPeopleRelationShip[51][51];

 

그 데이터를 가지고

진실을 아는 사람 배열 bArrVeraciousPeople을 찾은 다음

	// 진실을 아는 사람 모음 배열
	bool bArrVeraciousPeople[51];

진실을 아는 사람 배열 bArrVeraciousPeople과 party 데이터를 활용해

답을 출력했습니다.

 

회사 끝나고 야간에 하는 코딩이여서 정신이 헤롱헤롱했지만

다행이도 풀이는 성공했습니다.

 

전체코드는 아래와 같습니다.

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <stack>

using namespace std;

class CLierGame
{
private:

	// 사람과 사람이 맵핑된 2D 배열
	// 같이 파티에 간사람과 연결되 있으면 1 없으면 0
	int iArrPeopleRelationShip[51][51];
	
	// 진실을 아는 사람 모음 배열
	bool bArrVeraciousPeople[51];

	//
	bool visited[51];

	vector<string> partyData;

	int TotalNumberOfPeople;
	int TotalNumberOfParties;


public:
	CLierGame()
	{
		for (int i = 0; i < 51; i++)
		{
			visited[i] = false;
		}
	}
	~CLierGame()
	{

	}

	void inputRelationShips()
	{
		//파티의 갯수만큼 반복
		for (int i = 0; i < TotalNumberOfParties; i++)
		{
			string inputStr;

			std::getline(cin, inputStr);

			partyData.push_back(inputStr);

			int tempVal;
			stringstream ss(inputStr);
			// 첫번째 값은 버린다.
			ss >> tempVal;

			vector<int> tempVec;
			while (ss >> tempVal)
			{
				tempVec.push_back(tempVal);
			}


			for(auto el = tempVec.begin(); el != tempVec.end(); ++el)
			{
				for (auto el2 = tempVec.begin(); el2 != tempVec.end(); ++el2)
				{
					if (*el != *el2)
					{
						iArrPeopleRelationShip[*el][*el2] = 1;
						iArrPeopleRelationShip[*el2][*el] = 1;
					}

				}
			}
		}
	}

	void findVeraciousPeople()
	{
		for (int i = 0; i <= TotalNumberOfPeople; i++)
		{
			if (bArrVeraciousPeople[i] == true)
			{
				searchFn(i);
			}
		}
	}

	void searchFn(int val)
	{
		if (visited[val] == true)
		{
			return;
		}
		else
		{
			visited[val] = true;

			for (int i = 0; i <= TotalNumberOfPeople; i++)
			{
				if (iArrPeopleRelationShip[val][i] == 1)
				{
					bArrVeraciousPeople[i] = true;
					searchFn(i);
				}
			}
		}
	}


	void findAndPrintAnswer()
	{
		// 답
		int answer = getTotalNumberOfParties();


		//파티의 갯수만큼 반복
		for (int i = 0; i < TotalNumberOfParties; i++)
		{
			string inputStr = partyData[i];

			//cout << inputStr << endl;


			stringstream ss(inputStr);

			int tempVal;
			ss >> tempVal;

			while ((ss >> tempVal))
			{
				if (bArrVeraciousPeople[tempVal])
				{
					answer--;
					break;
				}
			}
		}

		cout << answer;
	}


	void inputTotalNumberOfPeopleAndParties()
	{
		// 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용
		string inputStr;
		std::getline(cin, inputStr);
		stringstream ss(inputStr);
		ss >> TotalNumberOfPeople;
		ss >> TotalNumberOfParties;

		for (int i = 0; i <= TotalNumberOfPeople; i++)
		{
			for (int j = 0; j <= TotalNumberOfPeople; j++)
			{
				iArrPeopleRelationShip[i][j] = 0;
			}
		}
	}

	void inputVeraciousPeople()
	{
		// 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용
		string inputStr;
		std::getline(cin, inputStr);
		stringstream ss(inputStr);
		int tempVal;
		ss >> tempVal;

		while ((ss >> tempVal)) {
			bArrVeraciousPeople[tempVal] = true;
		}
	}

	int getTotalNumberOfPeople()
	{
		return TotalNumberOfPeople;
	}

	int getTotalNumberOfParties()
	{
		return TotalNumberOfParties;
	}

	void printTestA()
	{
		for (int i = 0; i <= TotalNumberOfPeople; i++)
		{
			for (int j = 0; j <= TotalNumberOfPeople; j++)
			{
				cout << iArrPeopleRelationShip[i][j];
			}
			cout << endl;
		}
	}


	void printTestB()
	{
		for (int i = 0; i < 51; i++)
		{
			cout << bArrVeraciousPeople[i];
		}
	}
};

int main()
{
	// 객체 선언
	CLierGame* cLierGame = new CLierGame();

	// 최대 사람 수, 최대 파티의 갯수 입력
	cLierGame->inputTotalNumberOfPeopleAndParties();

	// 진실을 아는 사람 수와 아는 사람 번호 입력
	cLierGame->inputVeraciousPeople();

	// 관계 넣기
	cLierGame->inputRelationShips();

	// 진실을 아는 사람 찾기
	cLierGame->findVeraciousPeople();



	//cLierGame->printTestA();
	//cout << endl;
	//cLierGame->printTestB();


	 //답 찾기
	cLierGame->findAndPrintAnswer();

	return 0;
}

 

참고로 큰문제는 아니지만

영어로 

Lier는 누워있는 사람

Liar는 거짓말하는 사람 입니다.

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---