| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 28468 | 12654 | 9791 | 45.107% |
문제
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
답안
import sys
from collections import defaultdict
# initialize variables
num_people, num_party = map(int, sys.stdin.readline().split())
people_contaminated = [False] * (num_people+1)
party_contaminated = [False] * (num_party+1)
temp = list(map(int, sys.stdin.readline().split()))[1:]
if len(temp) != 0:
for contaminated_person in temp:
people_contaminated[contaminated_person] = True
people2party = defaultdict(lambda: [])
party2people = defaultdict(lambda: [])
for party_idx in range(1, num_party+1):
party_participants = list(map(int, sys.stdin.readline().split()))[1:]
for people_idx in party_participants:
people2party[people_idx].append(party_idx)
party2people[party_idx].append(people_idx)
people_investigated = [False] * (num_people+1)
party_investigated = [False] * (num_party+1)
next_investigated_parties = []
next_investigated_people = []
for people_idx in range(1, num_people+1):
if people_contaminated[people_idx]:
next_investigated_people.append(people_idx)
while next_investigated_people:
# investigate parties, using newly contaminated people info
while next_investigated_people:
people_idx = next_investigated_people.pop()
people_investigated[people_idx] = True
for party_idx in people2party[people_idx]:
if party_investigated[party_idx]:
continue
party_investigated[party_idx] = True
party_contaminated[party_idx] = True
next_investigated_parties.append(party_idx)
# investigate people, using newly contaminated parties info
while next_investigated_parties:
party_idx = next_investigated_parties.pop()
party_investigated[party_idx] = True
for people_idx in party2people[party_idx]:
if people_investigated[people_idx]:
continue
people_investigated[people_idx] = True
people_contaminated[people_idx] = True
next_investigated_people.append(people_idx)
print(num_party - len(list(filter(lambda x: x, party_contaminated[1:]))))풀이
파티에 참여하는 사람의 수와 파티의 수 자체가 50 이하로 그렇게 크지 않기 때문에, 문제 조건 그대로 구현하면 되는 문제라고 생각했다.
다만, 코로나 바이러스 확진자가 있을 때 역학조사를 하는 경우를 생각하는 게 더 쉬워서 contaminated, investigated와 같은 단어를 변수명에 사용했다.
진실을 알고 있는 파티 참여자가 있는 파티에서는 그 파티에 참여한 모두에게 진실을 말해야 하기 때문에, 코로나 확진자와 함께 있던 사람들을 격리해야 하는 것과 비슷하고,
진실을 아는 사람들이 다른 파티에 참여했다면 그 사람들까지 모두 격리해야 하는 것까지 비슷한 점들이 있기 때문이다.
나는 참여자가 주어지면 그 참여자가 참여했던 모든 파티를 알 수 있도록 저장한 맵과(참여자→파티), 파티가 주어지면 그 파티에 참여했던 모든 참여자를 알 수 있도록 저장한 맵(파티→참여자) 두 가지를 활용했다. 이를 이용해 나중에 더 쉽고 효율적으로 구현할 수 있다.
while next_investigated_people:
# investigate parties, using newly contaminated people info
while next_investigated_people:
people_idx = next_investigated_people.pop()
people_investigated[people_idx] = True
for party_idx in people2party[people_idx]:
if party_investigated[party_idx]:
continue
party_investigated[party_idx] = True
party_contaminated[party_idx] = True
next_investigated_parties.append(party_idx)
# investigate people, using newly contaminated parties info
while next_investigated_parties:
party_idx = next_investigated_parties.pop()
party_investigated[party_idx] = True
for people_idx in party2people[party_idx]:
if people_investigated[people_idx]:
continue
people_investigated[people_idx] = True
people_contaminated[people_idx] = True
next_investigated_people.append(people_idx)내가 구현한 것 중 가장 핵심이 되는 부분이다.
감염된 사람들의 리스트가 주어지면, 그 사람들이 갔던 파티를 찾고, 그 파티에 있던 사람들을 찾고, 그 사람들이 갔던 파티를 찾고, 사람들을 찾고, 파티를 찾고, … 하는 것을 반복하는 것이다.
더 감염될 사람이 없을 때까지 이 과정을 반복하면 된다.
그런데 이렇게 하면 사람A→파티A→사람B→파티A→사람A와 같이 사이클이 만들어질 수도 있기 때문에, investigated라는 boolean 배열을 만들어 조사를 마쳤는지 기록했다.
print(num_party - len(list(filter(lambda x: x, party_contaminated[1:]))))이런 과정을 거치면, 어떤 사람들이 감염된 사람들인지 알 수 있게 되고, 전체 파티의 수에서 감염된 사람들이 있는 파티의 수를 빼면 감염되지 않은 파티(모두가 진실을 알지 못해, 그 파티의 모든 참가자들에게 거짓말을 해도 그것을 알 수 없는 사람들만이 모여 있는 파티)들의 수를 구할 수 있다.
하지만 이 문제의 풀이를 더 검색해보니 더 나은 방법이 있었다.
union find를 이용하는 방법이었다.
union find의 개념을 찾아본 뒤에도 이 문제에 어떻게 union find를 적용할 수 있을지 잘 이해가 되지 않았었는데, 다음과 같은 과정을 거친다고 한다.
- 각 파티에 참여한 사람들을 각각의 그룹으로 만든다. (파티1=그룹1, 파티2=그룹2, …) ‘진실을 아는 사람’의 그룹도 만든다.
- 각 파티를 순회하면서, 파티에 ‘진실을 아는 사람’이 있다면 파티를 ‘진실을 아는 사람들’의 그룹에 흡수시킨다. (union)
- 각 파티를 순회하면서, ‘진실을 아는 사람’이 하나도 없는 파티의 숫자를 센다.
즉, 내가 구현했던 알고리즘에서는 특정 파티가 진실을 알게 되어야 하므로 그 파티의 참여자들이 다른 파티에 미치는 영향을 계속 고려해야 해서 여러 번씩 파티와 사람들을 순회했어야 했지만,
union find를 이용하게 되면서 파티의 개수만큼 두 번만 순회하더라도 문제를 풀 수 있게 되었다.
참여자들이 파티에, 파티가 참여자에 미치는 영향을 미리 계산해 그래프 혹은 set 자료구조에 저장하는 방법인 것이다.
2.번과 같이 그룹에 흡수시키는 방법은, 일반적인 union find 알고리즘을 이용하는 방법과, set을 이용하는 방법이 있었지만, 큰 개념상의 차이는 없었다.
(union find 알고리즘을 이용하는 방법)
# 출처:
# https://velog.io/@jiyoon9-velog/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-28%EC%9D%BC%EC%B0%A8-%EA%B1%B0%EC%A7%93%EB%A7%90%EC%9F%81%EC%9D%B4%EA%B0%80-%EB%90%98%EA%B8%B4-%EC%8B%AB%EC%96%B4-%EB%B0%B1%EC%A4%801043%EB%B2%88
N, M = map(int, input().split())
trueP = list(map(int, input().split())) # 진실을 아는 사람 저장
T = trueP[0]
del trueP[0]
result = 0
party = [[] for _ in range(M)]
def find(a): # find 연산
if a == parent[a]:
return a
else:
parent[a] = find(parent[a]) # 재귀 형태로 구현 -> 경로 압축 부분
return parent[a]
def union(a, b): # union 연산 대표 노드끼리 합치기
a = find(a)
b = find(b)
if a != b:
parent[b] = a
def checkSame(a, b): # 두 원소가 같은 집합에 속해 있는지 확인하는 함수
a = find(a)
b = find(b)
if a == b:
return True
return False
for i in range(M):
party[i] = list(map(int, input().split())) # 파티 데이터 저장
del party[i][0] # 맨 하단에 설명 적어둠!
parent = [0] * (N + 1)
for i in range(N + 1): # 대표 노드를 자기 자신으로 초기화
parent[i] = i
for i in range(M): # 각 파티에 참여한 사람들을 1개의 그룹으로 만들기
firstPeople = party[i][0]
for j in range(1, len(party[i])):
union(firstPeople, party[i][j])
# 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장할 수 없음
for i in range(M):
isPossible = True
cur = party[i][0]
for j in range(len(trueP)):
if find(cur) == find(trueP[j]):
isPossible = False
break
if isPossible:
result += 1 # 모두 다르면 결괏값 1 증가
print(result)(set을 이용한 방법)
# 출처:
# https://velog.io/@waveofmymind/%EB%B0%B1%EC%A4%80-1043.-%EA%B1%B0%EC%A7%93%EB%A7%90
n, m = map(int, input().split())
know = set(input().split()[1:])
parties = []
for _ in range(m):
parties.append(set(input().split()[1:]))
for _ in range(m):
for party in parties:
if party & know:
know = know.union(party)
cnt = 0
for party in parties:
if party & knowList:
continue
cnt += 1
print(cnt)union find는 두 정점이 같은 연결 그래프에 속해있는지 판별하는 그래프 알고리즘이지만, 이 문제에서처럼 하나의 덩어리를 몇 개의 그룹으로 나눠야 할 때 사용될 수도 있다.
다음에는 그룹을 나누는 문제를 접했을 때 union find를 적용할 수 있을지 확인해봐야겠다.
