[백준/C++] 1043번. 거짓말

문제

1043번: 거짓말

---

1. 첫 번째 풀이 (마지막 풀이)

사고 과정

- 진실을 아는 사람이 있다면 거짓말을 할 수 없다. 해당 파티는 제외한다.

- 해당 파티에 온 사람 역시 진실을 안 사람이 된다. 따라서 그 사람들이 온 파티 역시 제외한다.

- 이렇게 계속 제외하며 남은 파티의 개수를 출력한다.

- 근데 이거 사실상 그래프 아닌가?

- 인접행렬로 그래프를 구현하고 문제를 풀어보자. 큐를 사용하면 될 것 같다.

 

1. 2차원 벡터 2개 생성, 회원 당 파티 정보와 파티 당 회원 정보

2. 진실을 아는 사람들을 담아둘 큐 생성

3. 이미 확인한 사람을 체크하는 bool 배열 visited 생성

4. 거짓말해도 되는 파티인가?를 체크하는 정수 배열 lieParty 생성

5. 큐에 진실을 아는 사람들을 담아둔다.

6. 파티 당 회원 정보를 저장한다.

7. 회원 당 파티 정보를 저장한다.

8. 큐에서 하나를 빼내고, 해당 회원이 다닌 파티는 lieParty에 0으로 체크해둔다.

9. 해당 파티에 있는 회원들 중, 확인하지 않은 사람들을 큐에 담는다.

10. 큐가 빌 때까지 반복한다.

11. 거짓말해도 되는 파티의 수를 센다.

 

벌써부터 심상치 않은데?

 

코드

#include <stdio.h>
#include <vector>
#include <queue>

int main() {
	int n, m, truthCount, t, partyCount, num, answer = 0;
	scanf("%d %d", &n, &m);
	// 각 회원당 참여한 파티의 번호를 저장한다.
	std::vector<std::vector<int>> partyInfo(n + 1);
	// 파티 번호 / 각 파티 당 참여한 사람 번호
	std::vector<std::vector<int>> party(m);
	// 해당 사람을 체크했는가?
	std::vector<bool> visited(n + 1, false);
	// 거짓말해도 되는 파티인가?
	std::vector<int> lieParty(m, 1);
	// 진실을 아는 사람들을 담아둘 큐
	std::queue<int> truth;

	// truth에 진실을 아는 사람들을 담아둔다.
	scanf("%d", &truthCount);
	while (truthCount--) {
		scanf("%d", &t);
		truth.push(t);
	}

	// 파티 배열 생성
	for (int i = 0; i < m; i++) {
		scanf("%d", &partyCount);

		// 파티 정보 저장
		while(partyCount--) {
			scanf("%d", &num);
			party[i].push_back(num);
			// 회원별 참여한 파티 정보 저장
			partyInfo[num].push_back(i);
		}
	}

	// 큐가 빌 때까지 반복
	while (!truth.empty()) {
		// 방문한 사람 조회 후 저장
		int t = truth.front();
		truth.pop();
		visited[t] = true;

		// 해당 인원한 모든 파티에 대해
		// p: 파티 번호
		for (auto p : partyInfo[t]) {
			lieParty[p] = 0;

			// i: 파티에 참가한 사람 번호
			for (auto i : party[p]) {
				// 방문한 사람을 truth 큐에 등록
				if (visited[i] == false) {
					truth.push(i);
				}
			}
		}
	}

	// 한 번도 방문되지 않은 파티의 개수를 센다.
	for (int i = 0; i < m; i++) {
		answer += lieParty[i];
	}

	printf("%d", answer);
}

...와우.

 

결과

결과는 성공

---

개선

사고 과정

- 코드야 잘 돌아갔지만, 변수나 벡터가 너무 많아 이해하기 어렵다. 나도 코드짜면서 많이 헷갈렸다.

- 코드를 읽기 쉽게 리팩토링해보자.

- 회원당 파티 정보와 파티당 회원 정보는 통합할 수 있지 않을까? 2차원 벡터의 [i][j]중 i는 회원, j는 파티처럼해서?

- 아예 하나의 2차원 배열로 모든 걸 해결할 순 없을까?

- 어차피 회원 번호가 1부터 시작하니, 0행은 버려진다. 이를 lieParty로 쓰면 될 것 같다.

- visited는? 파티도 1부터 시작시키면 가능하다.

- 5명의 사람, 5개의 파티를 표로 정리하면

회원\파티	0 (visited)	1	2	3	4	5
0 (lieParty)	1	1	1	1	1	1
1	0	0	0	0	0	0
2	0	0	0	0	0	0
3	0	0	0	0	0	0
4	0	0	0	0	0	0
5	0	0	0	0	0	0

이렇게 사용이 가능하다.

- 작성은 완료했지만, 표를 봐가며 작성해야했다. 코드만 보는 경우 해석이 쉽지 않을 테니 좋은 패턴은 아닌 것 같다.

- int 변수가 너무 많아 줄이고 싶지만, 재사용하자니 이름이 헷갈리고, 냅두자니 선언문이 너무 길었다.

- num과 t는 num으로 통합한 후 재사용이 가능해보였다. 애초에 둘 다 번호를 뜻하며, scanf를 위한 변수기에 헷갈려도 상관이 없었다. 또 큐를 돌리는 과정에서 int t를 따로 선언했기에, 중복되는 상태였다.

- 사용 직전 선언하는 방법과 현상 유지를 고민했으나, 변수 선언 위치가 제각각인 게 더 복잡할 것 같아 냅두기로 했다.

- for (auto i : vector)를 써보려했지만, 숫자가 1부터 시작하기에 마땅한 곳은 없었다. 그대로 마지막에만 쓰기로 했다.

- true와 false는 모두 1과 0으로 대체했으며, if문 내에 일부러 == 1, == 0을 넣어 판별하기 쉽게 했다.

- if문을 삼항 연산자로 통합할 부분도 없다.

- count를 계산하는 과정은 합칠 수 있어보였다. +대신 -를 사용해, 거짓말 할 수 없는 파티가 생기면 1씩 감소시켰다. 거짓말 불가 파티가 가능 파티로 변하진 않으니까.

- n, m은 별도로 분리하고, 입력받은 다음 나머지 변수들을 선언했다.

- 큐를 돌리는 조건에, 위 코드에선 lieParty[p] = 1, 아래 코드에선 info[0][p] = 0인 부분을 조건문에도 포함시켰다. 이로써 해당 회원이 방문한 파티가 이미 거짓말 불가 파티라면(해당 파티를 이미 순회해봤다면), 그 파티에 대해 2번 순회하지 않게 됐다. 연산량이 꽤나 줄었을 것이다.

 

코드

 

#include <stdio.h>
#include <vector>
#include <queue>

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	int truthCount, partyCount, num, count = m;
	// 회원 / 파티 정보, 0행: 거짓말 가능 파티 정보, 0열: 방문 회원 정보
	std::vector<std::vector<int>> info(n + 1, std::vector<int>(m + 1, 0));
	// lieParty는 전부 1로 초기화 (0번 제외)
	std::fill(info[0].begin() + 1, info[0].end(), 1);
	// 진실을 아는 사람들을 담아둘 큐
	std::queue<int> truth;

	// truth에 진실을 아는 사람들을 담아둔다.
	scanf("%d", &truthCount);
	while (truthCount--) {
		scanf("%d", &num);
		truth.push(num);
	}

	// 파티 정보 저장
	for (int i = 1; i <= m; i++) {
		scanf("%d", &partyCount);
		while(partyCount--) {
			scanf("%d", &num);
			info[num][i] = 1;
		}
	}

	// 큐가 빌 때까지 반복
	while (!truth.empty()) {
		// 방문한 사람 조회 후 저장
		int t = truth.front();
		truth.pop();
		info[t][0] = 1;

		// 해당 인원이 참여한 모든 파티에 대해 (p: 파티 번호)
		for (int p = 1; p <= m; p++) {
			if (info[t][p] == 1 && info[0][p] == 1) {
				// 파티가 거짓말 불가임을 체크
				info[0][p] = 0;
				count -= 1;

				// i: p번 파티에 참가한 사람 번호
				for (int i = 1; i <= n; i++) {
					// 방문하지 않은 사람을 truth 큐에 등록
					if(info[i][p] == 1 && info[i][0] == 0) {
						truth.push(i);
					}
				}
			}
		}
	}

	printf("%d", count);
}

원래 백준에 제출할 땐 주석을 지웠는데, 이젠 그냥 같이 올리기로 했다.

 

결과

리팩토링이 로직은 건들지 않았다. 메모리는 4 KB 감소했으며, 코드 길이도 약간 더 짧아졌다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/2946903

jklee06s님의 코드. 순위 자체는 더 높은 C++ 코드가 있지만, 변수명이 죄다 한 글자라 그냥 넘겼다. 3등에 랭크

 

내 코드와 비교

- BFS를 따로 함수로 빼셨다.

- 나는 count를 m에서 1씩 줄이는 방식, 이 분은 0에서 1씩 증가시키는 방식. 마지막에 m - sol로 출력하셨다.

- 2차원 배열로 행은 파티, 열은 사람으로 두되, 진실을 아는 사람과 파티 배열은 따로 구현하셨다.

- '진실을 아는 사람'이 곧 BFS의 visited 역할을 한다.

- queue를 직접 구현하셨다. C언어를 선택하셨기 때문으로 보인다.

---

강평

짧은 코드보다 정확한 구현에 집중할 수 있었던 문제. 처음엔 사람만 저장하는 그래프로 접근해서 풀었는데, 출력이 다르게 나오는 걸보고 파티 벡터도 따로 구현했다.

모든 코드가 한 두 줄로 끝날 수야 없는 노릇이기에, 어쩌면 이런 코드가 당연한 걸수도 있다. 그렇기에 얼마나 주석을 잘 달았느냐가 퀄리티를 좌우한다고 생각한다. 개념 떠올리기보단 구현이 더 까다로웠던 문제.