[BOJ] 1043 : 거짓말 [그래프](Python)

문제 링크

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

1043번: 거짓말

소스 코드

from collections import deque

n,m = map(int,input().split())
trues = list(map(int,input().split()))
knows = [False for _ in range(n+1)] # 진실을 아는 사람 체크
graph = [[] for _ in range(n+1)] # 사람 간 연결 그래프
parties = [] # 파티별 구성원 리스트

for idx in range(m):
    tmp_list = list(map(int,input().split()))
    num,people = tmp_list[0],tmp_list[1:]
    parties.append(people) # 파티 참여자 기록
    for i in range(len(people)):
        for j in range(i+1,len(people)): # 양방향 간선
            graph[people[i]].append(people[j])
            graph[people[j]].append(people[i])
graph = [list(set(x)) for x in graph] # 중복 제거

if trues == [0]: # 진실을 아는 사람이 없는 경우
    print(m)
    exit(0) # 프로그램 종료

for true in trues[1:]: # 진실을 아는 사람은 체크
    knows[true] = True

def bfs(x): # type(x) - list
    queue = deque(x) # 진실을 아는 사람 리스트
    while queue:
        cur = queue.popleft()
        for next in graph[cur]:
            if not knows[next]:
                knows[next] = True # 진실을 아는 사람으로 추가
                queue.append(next) # 이 사람이 만날 사람 추가 탐색

# 처음부터 진실을 아는 사람들 리스트
bfs([x for x in range(1,len(knows)) if knows[x]])
# 0번을 제외한 숫자만 추출
knows = [x for x in range(1,len(knows)) if knows[x]]

cnt = 0 
for party in parties: # 각 파티별로
    if not (set(party) & set(knows)): # 아는 사람이 하나도 없다면
        cnt += 1 # 과장된 이야기 할 수 있는 파티 개수 증가
print(cnt)

 

해설

• BFS, 그래프탐색

조금 난잡하게 코드를 작성하게 되었네요.

지금보다는 직관적으로 다듬고 싶긴 했는데 귀찮으니 일단 패스... 😎

 

1) 입력 받기

다른 문제들과 달리 조금 조심해야 하는 점은 '인원'과 '명단'을 한 줄에 같이 준다는 것입니다.

따라서 슬라이싱을 통해 두 개를 구분한 것을 확인하실 수 있습니다.

tmp_list = list(map(int,input().split()))
num,people = tmp_list[0],tmp_list[1:]

 

그렇기 때문에 중간에 

if trues == [0]: # 진실을 아는 사람이 없는 경우
    print(m)
    exit(0) # 프로그램 종료

이런 코드를 삽입해서 인덱스 에러가 발생하지 않도록 한 것입니다.

 

2) 그래프 생성하기

우리가 하고 싶은 것은 '진실을 아는 사람'이 누구를 만났는지, 그래서 '진실을 알게 된 사람은 누구를 만났는지' ... 의 무한 반복일 것입니다.

그렇기 때문에 각 사람이 파티에서 누구를 만나게 되는지를, 즉 연결 관계를 그래프로 표현하면 되겠습니다.

한 파티에서 여러 명이 만날 수 있으므로 이중 for문을 사용하여 서로서로 연결 관계를 추가해줍니다.

이때 양방향 간선임을 잊으면 안 됩니다!

 

예를 들어 1번 사람과 2번 사람이 만나게 된다면 1,2 번 모두 추가해줘야 합니다.

for i in range(len(people)):
    for j in range(i+1,len(people)): # 양방향 간선
        graph[people[i]].append(people[j])
        graph[people[j]].append(people[i])

 

3) BFS

연결 관계는 다 파악했으니, 맨 처음 진실을 알고 있는 사람을 기준으로 그래프를 탐색합니다.

knows 리스트에는 각 사람이 진실을 알고 있는지 여부에 따라 True, False가 할당되어 있습니다.

 

만약 graph의 연결 관계를 통해 진실을 알게 되면 knows의 False를 True로 바꿔줍니다.

진실을 알게 된 사람은 다시 queue에 추가하여 그 사람이 만나게 되는 사람들을 추가로 탐색하며 위 과정을 반복합니다.

def bfs(x): # type(x) - list
    queue = deque(x) # 진실을 아는 사람 리스트
    while queue:
        cur = queue.popleft()
        for next in graph[cur]:
            if not knows[next]:
                knows[next] = True # 진실을 아는 사람으로 추가
                queue.append(next) # 이 사람이 만날 사람 추가 탐색

 

4) 결과 추출

각 파티에 참여한 사람들을 확인하여 참여한 어떤 사람도 진실을 아는 사람이 없어야 합니다.

이를 set(참여자) & set(진실을 아는 사람들) 를 사용하여 확인하고 만약 공통된 내용이 없으면 count를 올려줍니다.

cnt = 0 
for party in parties: # 각 파티별로
    if not (set(party) & set(knows)): # 아는 사람이 하나도 없다면
        cnt += 1 # 과장된 이야기 할 수 있는 파티 개수 증가