[kata][python] 백준 알고리즘 1043번 문제 (거짓말)
- 7 mins거짓말
출처: 백준 알고리즘 1043번 문제
문제
지민이는 파티에 가서 이야기 하는 것을 좋아한다.
파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다.
지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다.
당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다.
하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다.
문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다.
따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다.
당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도
지민이는 거짓말쟁이로 알려지게 된다.
지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다.
그리고 그 이야기의 진실을 아는 사람이 주어진다.
그리고 각 파티에 오는 사람들의 번호가 주어진다.
지민이는 모든 파티에 참가해야 한다.
이때, 지민이가 거짓말쟁이로 알려지지 않으면서,
과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다.
진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다.
사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고,
진실을 아는 사람의 수와 각 파티마다 오는 사람의 수는 모두 0 이상 50 이하의 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제입력
4 3
0
2 1 2
1 3
3 2 3 4
예제출력
3
내 풀이1(오답)
1 import sys
2
3 cnt_people, cnt_party = map(int, sys.stdin.readline().rstrip().split())
4 witness_set = set(sys.stdin.readline().rstrip().split()[1:])
5 cnt_possible_lie = 0
6
7 for i in range(cnt_party):
8 attendee_set = set(sys.stdin.readline().rstrip().split()[1:])
9 if witness_set.intersection(attendee_set):
10 witness_set = witness_set.union(attendee_set)
11 else:
12 cnt_possible_lie += 1
13
14 print(cnt_possible_lie)
처음에 너무 단순하게 생각했다.
(4) 이미 진실을 알고있는 “증인 set” (witness_set)을 만들었다.
(5) 거짓말이 가능한 파티의 숫자 (cnt_possible_lie)를 0으로 초기화했다.
(8~10) “파티 참석자 set” (attendee_set)을 만들고, 앞에서 만든 증인 set과 겹치는 부분이 있다면, 해당 참석자 set은 모두 기존의 증인셋에 통합(union) 해주었다. (진실을 듣게된 이들은 모두 증인이 되므로)
(11~12) 그렇지 않은 경우에는(파티 참석자에 증인이 포함되지 않은 경우에는) 거짓말이 가능한 파티의 숫자에 1을 더해주었다.
이 방법은 얼핏 정답처럼 보이지만, 헛점이 있다.
“나에게 거짓말을 들은 사람들이 다른 파티에서 진실을 알고있는 사람과 만날 경우” 를 고려하지 않은 것이다.
그리고 다시 그 파티에서 만난 사람들끼리 수군수군(?)대며 입소문이 퍼질 것을 고려하지 못한것이다.
즉, 입력되는 순서대로 한 파티가 끝나고 다른 파티가 열리는 것이 아니라,
입력된 모든 파티가 동시에 열리고 있다고 봐야한다.
따라서 진실을 알고있는 그 누구에게도 들키지 않고 최대한 안전하게(?) 거짓말을 하기 위해서는,
“나에게 한 번이라도 진실을 들은 사람은 그가 참석한 모든 파티에 진실을 퍼트릴 것이라고 가정해야한다.”
말로만 하면 헷갈릴수 있으니 예를 들자.
예를들어 증인은 “1번” 한 명, 파티는 5개 열린다고 가정하고,
참석자의 set이 다음과 같다고 가정하자.
파티(가) : {5, 6}
파티(나) : {4, 5}
파티(다) : {3, 4}
파티(라) : {2, 3}
파티(마) : {1, 2}
내 알고리즘대로 풀면 오직 (마) 에서만 진실을 이야기하고,
나머지 (가), (나), (다), (라) 에서는 모두 거짓말이 가능하다.
진실을 알고있는 증인 1번은 (마)에만 참석했으니까.
하지만 이는 아주 위험한 행동이다.
생각해보자.
내가 (가), (나), (다), (라)에서 거짓말을하고 (마) 에서만 진실을 말했다고 치자.
이 때, “2번”은 이상한점을 느꼈을 것이다.
왜냐면 (라) 파티에서는 나에게 거짓말을 들었으니까!
이를 이상하게 여긴 2번은, (라) 파티에 함께 참석한 3번에게 내가 거짓말쟁이였던것을 전달할 것이다.
여기서 끝나면 얼마나 좋을까?
이를 전달해들은 3번은 (다) 파티에 같이 참석했던 4번에게 다시 나의 소문을 퍼트릴 것이며,
4번은 다시 (나) 파티에 같이 참석했던 5번에게 전달,
5번은 다시 (가) 파티에 같이 참석했던 6번에게 전달할 것이다.
결국 1번부터 6번까지 모두 나를 거짓말쟁이로 생각하게 될 것이다.
한 명에게도 거짓말쟁이가 되어선 안되는데 모두에게 거짓말쟁이가 되어버린 것이다 ㅜㅜ
내 풀이2(정답)
코드를 올리기 전에 우선 사고의 흐름부터 적어보자.
거짓말쟁이가 되지 않고 최대한 많은 파티에서 거짓말을 치려면 어떻게 해야할까 생각해봤다.
어찌보면 단순 무식하지만 방법은 하나였다.
앞선 예제로 다시 생각해보자.
증인 : {1}
파티(가) : {5, 6}
파티(나) : {4, 5}
파티(다) : {3, 4}
파티(라) : {2, 3}
파티(마) : {1, 2}
일단 파티 리스트를 (가)부터 (마)까지 쭉 훑어보는것이다.
그러다보면 처음에 진실을 알고있던 증인(1번)과 같은 파티에 참석한 사람이 있을것이다.
해당 예제에서는 바로 (마) 파티에 참석한 2번이다.
일단 2번을 다시 새로운 증인 리스트에 포함시키고, 다시 (가) 부터 (마) 까지 쭉 훑어본다.
증인 : {1, 2}
파티(가) : {5, 6}
파티(나) : {4, 5}
파티(다) : {3, 4}
파티(라) : {2, 3}
파티(마) : {1, 2}
이번에는 (라) 파티에서 새로운 증인 2번이 발견되었고,
2번과 같은 파티에 참석한 3번 또한 새로운 증인 리스트에 포함시키도록 한다.
그리고 다시 (가) 부터 (마) 까지 쭉 훑어본다.
증인 : {1, 2, 3}
파티(가) : {5, 6}
파티(나) : {4, 5}
파티(다) : {3, 4}
파티(라) : {2, 3}
파티(마) : {1, 2}
이런식으로 총 파티의 숫자만큼 for문을 돌며 (가) ~ (마) 까지 훑어보게 되면,
모든 증인들의 리스트를 뽑아내어 완벽히 위험을 제거할 수 있다.
이렇게 하면, 해당 예제의 경우 거짓말을 할 수 있는 파티의 수는 0이 된다.
이 로직을 기억하고, 이제 코드를 보자.
1 import sys
2
3 cnt_party = int(sys.stdin.readline().rstrip().split()[1])
4 witness_set = set(sys.stdin.readline().rstrip().split()[1:])
5
6 party_list = []
7 possible_list = []
8
9 for _ in range(cnt_party):
10 party_list.append(set(sys.stdin.readline().rstrip().split()[1:]))
11 possible_list.append(1)
12
13 for _ in range(cnt_party):
14 for i, party in enumerate(party_list):
15 if witness_set.intersection(party):
16 possible_list[i] = 0
17 witness_set = witness_set.union(party)
18
19 print(sum(possible_list))
(9~10) 참가자들을 분석하기위해 파티 리스트를 만들었다.
(11) 우선 파티의 갯수만큼 possible_list 에 숫자 1을 채워주었다. 만약 특정 파티에서 거짓말이 불가능하다고 판단될 경우, 해당하는 칸을 0으로 바꿔줄 것이다 (16번 라인 참고)
(13~17) 앞서 설명했듯이, (가) ~ (마) 파티를 돌며 증인을 추가하며 반복적으로 검증하는 부분을 코드로 구현한 것이다.
- (13) 일단 파티의 갯수만큼 for문을 돌린다.
- (14) 각 for문마다 모든 파티 리스트를 분석하며,
- (15) 만약 증인이 특정 파티에 존재할 경우,
- (16) 해당 파티에서는 거짓말이 불가능하므로 possible_list의 해당 인덱스를 0으로 바꾼다.
- (17) 그리고 해당 파티에 참석한 모든 인원을 증인 리스트에 추가해준다.
(19) 모든 검증을 끝낸 후에도 possible_list에 1로 남아있는 부분은 거짓말이 가능한 파티이므로, possible_list의 모든 합을 출력해주면된다.
분석
생각이 좀 필요한 문제였다.
처음엔 너무 쉽게 생각했다가,
어찌보면 나중엔 너무 어렵게 생각했던 것 같기도 하다.
문제를 풀고 다른사람들은 어떻게 풀었나 봤더니 그래프의 연결성(?)을 이용해서 풀었더라.
증인과 그와 접촉했던 모든 사람들을 연쇄적으로 연결하고,
연결된 노드를 거짓말 파티에서 제외하는 식으로 풀었다. (내가 개념이 부족해서 설명이 빈약하다)
어쨌든 로직 자체는 내가 푼것과 거의 같다고 보면 되지만,
개념적인 기반이 탄탄해보였고, 때문에 설명도 더 깔끔했기에 보다 전문적으로 느껴졌다.
다른 풀이가 궁금하면 여기 링크 걸어놓은 “빰” 님 브로그 에서 확인해보길 바란다.
그리고 한 번 거짓말을 하게되면 마치 암세포가 퍼지듯 그 사람이 만나는 수많은 사람에게 나의 거짓말이 전파(?)된다는 뜻밖의 교훈도 얻을 수 있었는데,
블로그를 하다가 혹시 잘못된 정보를 올려 이와 비슷한 사단을 내지 않도록 충분한 공부가 필요하다는 생각이 들었다.
전혀 상상하지 못한 곳에서 전혀 상상하지 못한 교훈을 얻게되는것 또한 코딩의 매력이 아닐까 싶다.
단순히 알고리즘을 풀어내는 것 뿐 아니라 스토리 속에서 교훈을 얻을 수 있는 좋은 문제를 만들어준 백준님께도 감사의 말씀 올린다.
코딩장이
-장이: [접사] ‘그것과 관련된 기술을 가진 사람’의 뜻을 더하는 접미사.