[백준] 1043 거짓말 (python 파이썬)

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

1043번: 거짓말

---

아이디어

1. 반복문

• 문제 느낌이 진실을 아는 사람이 좀비같이 감염시키는 것이라 생각
• 그래서 진실을 아는 사람과 같이 있는 사람들을 진실을 아는 사람으로 바꿨다.
• 근데 이러면 진실을 아는 사람들이 바뀌어서 전체 파티를 또 탐색해야 하고 이를 계속 반복해야 해서 실패했다.

2. 그래프

• 그러다가 동시에 한 번에 해야 된다는 것을 깨닫고 그래프를 사용하기로 결정
• 각 파티마다 있는 사람들을 두 명씩 양방향으로 이어주는 걸로 그래프를 만들었다.
• 그리고 처음 진실을 아는 사람들로 시작해 탐색을 하면 한 번에 진실을 아는 사람들을 모두 찾을 수 있다.

 

 

---

전체 코드

import sys
from collections import deque
from itertools import combinations

N, M = map(int,input().split())
ans = 0
truth_flag = False
party_list = []
who_know_truth = [False] * (N + 1)

know = [int(x) for x in sys.stdin.readline().rstrip().split()]
know_member = know[1:]

for k in know_member:
    who_know_truth[k] = True

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    party = [int(x) for x in sys.stdin.readline().rstrip().split()]
    party_member = party[1:]
    party_list.append(party_member)
    for pair in combinations(party_member,2):
        if not pair[1] in graph[pair[0]]:
            graph[pair[0]].append(pair[1])
        if not pair[0] in graph[pair[1]]:
            graph[pair[1]].append(pair[0])

def bfs(n):

    deq = deque()
    deq.append(n)
    visited[n] = True

    while deq:
        x = deq.popleft()

        for i in graph[x]:
            if not visited[i]:
                who_know_truth[i] = True
                visited[i] = True
                deq.append(i)

for i in know_member:
    visited = [False] * (N + 1)
    bfs(i)

ans = M
for party in party_list:
    for p in party:
        if who_know_truth[p] == True:
            ans -= 1
            break
print(ans)

---

코드 설명

who_know_truth = [False] * (N + 1)

know = [int(x) for x in sys.stdin.readline().rstrip().split()]
know_member = know[1:]

for k in know_member:
    who_know_truth[k] = True

처음에 진실을 아는 사람들을 줄로 입력받으면 리스트 맨 앞에는 사람 수 이므로 슬라이싱 해준다.

그리고 진실을 아는 사람의 번호는 True로 표시해준다.

 

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    party = [int(x) for x in sys.stdin.readline().rstrip().split()]
    party_member = party[1:]
    party_list.append(party_member)
    for pair in combinations(party_member,2):
        if not pair[1] in graph[pair[0]]:
            graph[pair[0]].append(pair[1])
        if not pair[0] in graph[pair[1]]:
            graph[pair[1]].append(pair[0])

그래프 만드는 파트다.

여기서도 슬라이싱 해주고 전체 파티 리스트에 추가해둔다.(나중에 필요)

 

그리고 조합 함수를 사용해서 2명씩 페어를 만들어 인접 리스트에 추가해준다.

 

 

def bfs(n):

    deq = deque()
    deq.append(n)
    visited[n] = True

    while deq:
        x = deq.popleft()

        for i in graph[x]:
            if not visited[i]:
                who_know_truth[i] = True
                visited[i] = True
                deq.append(i)

for i in know_member:
    visited = [False] * (N + 1)
    bfs(i)

진실을 아는 사람들을 기준으로 그래프 탐색을 해준다.

방문을 할 때마다 진실을 아는 사람으로 바꿔준다.(False -> True)

 

ans = M
for party in party_list:
    for p in party:
        if who_know_truth[p] == True:
            ans -= 1
            break
print(ans)

그리고 각 파티마다 진실을 아는 사람이 한 명이라도 존재하면 break 하고 파티 총개수에서 -1 해준다.