백준 1043번 : 거짓말 - 파이썬

문제

 

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

정답

N, M = map(int,input().split())
know_list = list(map(int,input().split()))
party_list = []
for i in range(M):
    tmp_list = list(map(int,input().split()))
    party_list.append(tmp_list)
 
del know_list[0]
for i in party_list:
    del i[0]
 
party_list_carbon = list(party_list)
stop = 0
while stop != 1:
    know_yes = False
    new_know_list = 0
    for i in party_list:
        for j in i:
            if j in know_list:
                know_yes = True
                party_list_carbon.remove(i)
                new_know_list=(i)
                break
        if know_yes:
            for k in new_know_list:
                if k not in know_list:
                    know_list.append(k)
    if party_list_carbon == party_list:
         stop = 1
    party_list = list(party_list_carbon)
 
print(len(party_list))

#1~2 : N, M은 일반 정수로 입력받고 know_list로 진실을 아는 사람들의 수와 번호를 입력받음

#3~6 : party_list를 list로 선언하고 M번 map형식으로 입력받는데 한 줄을 list로 묶고 party_list에 넣어서 2차원 list를 만든다

#8~10 : 여기서 각 list들의 첫번째 요소인 사람 수는 의미 없으므로 del을 활용해 제거

#12 : for문 중에서 요소를 제거하면 index가 밀리기 때문에 사본을 만듬

#13 : stop은 while문을 정지하기 위한 변수

#14~30 : while문 시작

#15 : know_yes는 만약 파티 중에서 진실을 아는 사람이 있다면 True가 된다.

#16 : party_list가 2차원 리스트이기 때문에 해당 요소 하나를 꺼내면 list가 되기 때문에 list로 선언하지 않았음

#17~27 : party_list 검사 시작

#18 : party_list의 list 한 묶음에서 하나의 정수를 꺼내옴

#19 : 정수 j가 만약 진실을 아는 사람들 중 하나라면

#20 ~ 23 : know_yes를 True로 만들어서 #24의 조건문을 True로 만들 것이고

2차원 리스트의 party_list_carbon에서 list i를 제거

new_know_list는 진실을 알게된 사람들의 리스트를 추가하는 것임

이미 사실을 알게된 사람들이 있으니까 i는 이제 볼 필요가 없음

#24 ~ 26 : 새로 알게된 사람들이 존재한다면

new_know_list에서 사람들을 하나씩 꺼내서 기존 know_list와 비교하고 중복요소가 아니라면 추가

#28 ~ 29 : 기존 party_list와 사본 party_list_carbon이 서로 같다면 이는 새로운 진실을 알게되는 파티가 없다는 것이니 while문 중지

#30 : 다시 업데이트된 원본과 사본을 같게 만듬

예제 입력 1

4 3
0
2 1 2
1 3
3 2 3 4

예제 출력 1 

3

 

예제 입력 4 

4 5
1 1
1 1
1 2
1 3
1 4
2 4 1

예제 출력 4 

2

예제 입력 5 

10 9
4 1 2 3 4
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4

예제 출력 5 

4

예제 입력 6 

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

예제 출력 6 

5