1043-python

r

문제를 해석해보면 각라인에 파티가 있는데 그 중 진실을 아는 사람이 하나라도 있으면 그 파티에서는 지민이는 거짓말쟁이로 판단되어진다. 그래서 생각한것이 Union&find를 떠올렸다. 파티에 잇는 사람들을 노드들로 생각하고 잇고 나서 find를 통해 만약 진실을 아는 사람이 있으면 그 연결한 노드들에서는 거짓말을 하면 안되는 것이다. 

예제4

import sys
input  = sys.stdin.readline
N,M = map(int,input().split())
peoplelist = list(map(int,input().split()))[1:]
uplist = [i for i in range(N+1)]

for i in peoplelist:
    uplist[i] = 0 #정답을 아는놈드은 0으로

def Union(a,b):
    x,y = find(a),find(b)
    if(x<y):
        uplist[y]=x
    else:
        uplist[x] = y
def find(x):
    if x == uplist[x]:
        return x
    return find(uplist[x])
party = []
for k in range(M):
    partylist = list(map(int,input().split()))[1:]
    party.append(partylist)
    for i in range(len(partylist)-1):
        Union(partylist[i],partylist[i+1])
        
ans = 0
for par in party:
    for i in par:
        if (find(i)==0):
            break
        else:
            ans+=1
print(ans)

1트 실패. 해설을하자면 진실을 아는 사람들은 uplist의  값을 0으로 초기화 하고 그 이후 파티리스트를 받으며 각 파티 참여인원을 union해주어 선을 이어준다. 파티라는 리스트에 추가해주고 마지막에 이중 포문을 돌면서 각 파티들을 하나씩 꺼내면서 파티에 있는 참여인원중 find해준것이 0이면 break으로 탈출! 아니라면 정답에 +1해주는 코드이다. 그런데 문제가 생겼다. 답이 틀리다. 그 이유를 찾아보니 마지막에서 if(find해주어서 0일경우만 탈출시키고 아니라면 정답에 1을 추가해주었는데 이러면 만약 파티인원이 두명인데 그 두명모두 find가 0이아니라면 각각의 인원이 추가되어버리면서 ans이 정답보다 많게 나온다. 그래서 고쳐준 코드가

import sys
input  = sys.stdin.readline
N,M = map(int,input().split())
peoplelist = list(map(int,input().split()))[1:]
uplist = [i for i in range(N+1)]

for i in peoplelist:
    uplist[i] = 0 #정답을 아는놈드은 0으로

def Union(a,b):
    x,y = find(a),find(b)
    if(x<y):
        uplist[y]=x
    else:
        uplist[x] = y
def find(x):
    if x == uplist[x]:
        return x
    return find(uplist[x])
party = []
for k in range(M):
    partylist = list(map(int,input().split()))[1:]
    party.append(partylist)
    for i in range(len(partylist)-1):
        Union(partylist[i],partylist[i+1])
        
ans = 0
for par in party:
    lie = True
    for i in par:
        if (find(i)==0):
            lie = False
            break
    if(lie == True):
        ans+=1
print(ans)

마지막에 lie라는 변수를 설정해주고 진실을 아는 사람이 없는 파티에서만 ans+=1을해주어 정답을 제대로 세줄수 있었다.