Python에서 제공하는 Set 자료구조를 활용하여 문제를 풀었다.
하지만 이 외에도 Union-Find 알고리즘으로도 풀이가 가능하다.
이번 문제는 Set 자료구조와 교집합, 합집합 연산을 통해 구현이 가능했다.
하지만 Union-Find 라는 알고리즘 또한 활용이 가능하다는 것을 알았다.
Set 자료구조와 교집합, 합집합 연산을 통해 구현이 가능했다.
파티에 참여한 인원 N
과 M
개의 파티가 개최되었다.
파티에서 진실을 아는 인원이 있다면, 나머지 구성원들 또한 진실을 알게 된다.
지민이는 모든 파티를 순회하며 거짓말을 최대한 많이 해야만 싶다.
즉 진실을 모르는 이들만 모인 그룹을 찾아야 거짓말을 전파해야 한다.
따라서 처음에는 집합 (Set) 을 활용해야 하는 문제라고 생각했다.
import sys
read = sys.stdin.readline
N, M = map(int, read().split())
know_true = set(read().split()[1:])
parties = [set(read().split()[1:]) for _ in range(M)]
for party in parties:
if know_true.intersection(party):
know_true = know_true.union(party)
result = 0
for party in parties:
if not know_true.intersection(party):
result += 1
print(result)
접근은 좋았으나, 이 코드는 입력 순서 에 따른 오류를 잡지 못했다.
처음에는 모든 파티의 구성원 정보를 전부 입력 받은 후, 이를 한 번 순회하였다.
순회 과정에서 진실을 알게 된 이들과 동행한 사람들도 진실을 알게 되었으므로
해당 동행한 이들을 모두 합집합 연산 (union) 을 통해 포함시켰다.
그리고 다음 줄에는 다시 모든 파티를 순회하면서 최종적으로 산출된 집합을 통해
진실을 아는 이들이 파티에 섞여 있는지를 체크했다. 하지만 오답 처리를 받았다.
그 이유는 새롭게 진실을 알게 된 이들을 고려하지 않고, 연산을 진행했기 때문이다.
아래의 예시가 바로 내가 세운 코드의 반례였다.
4 6
1 1
1 4
1 3
2 2 4
1 2
2 2 3
2 4 1
기대한 값은 0 이였으나, 어째서인지 3 이 나온다.
위 예시에서 진실을 아는 이는 1번
이며, 이후 1번
은 4번
과 만나 진실을 듣는다.
그리고 4번
은 2번
과 만났기 때문에 지민이는 거짓말을 할 수 없는 게 정상이다.
하지만 상단의 코드에서는, 진실을 아는 이들을 추려내는 과정에서 이를 고려하지 않는다.
즉, 앞서 입력된 4번
과 2번
이 참석한 파티에서는 거짓말을 해도 된다고 판단한 것이다.
정석대로라면 1번
은 4번
과 진실을 듣고, 4번
은 2번
과 진실을 들어야 정상인데,
단순히 입력받은 순서대로만 이를 처리하면 1번
과 4번
만 진실을 들었다고 처리한다.
그렇다면 지민이는 2번
과 3번
이 모인 자리에서 안일하게 거짓말을 하다 들킬 것이다.
import sys
read = sys.stdin.readline
N, M = map(int, read().split())
know_true = set(read().split()[1:])
# 파티 그룹을 우선 집계하여 이를 체크.
parties = [set(read().split()[1:]) for _ in range(M)]
# 파티를 진행하면서, 진실을 알게 된 이들을 체크.
for _ in range(M):
for party in parties:
# 파티 인원 중, 진실을 아는 이들이 있다면 모든 참가자를 포함시킴.
if know_true.intersection(party):
know_true = know_true.union(party)
print(know_true)
# 파티 구성원 중, 진실을 알게 된 이들이 포함되지 않은 파티만 체크.
result = 0
for party in parties:
if not know_true.intersection(party):
result += 1
print(result)
결국 거짓말을 하면 안되는 인물을 추가 반복을 통해 파악해야 했다.
따라서 정확하게 이를 해결하려면 파티의 수 (M) 만큼 탐색 과정을 또 거쳐야 한다.
그래야만 새롭게 진실을 전달받은 이들에 대해서도 올바르게 탐색을 마칠 수 있다.
import sys
# x 노드가 속한 집합의 루트 노드를 탐색하는 함수.
def find(x):
if x != parents[x]:
parents[x] = find(parents[x])
return parents[x]
def union(a, b):
a, b = find(a), find(b)
# 둘 다 진실을 아는 경우, 굳이 Union을 안해도 됨.
if a in know_true and b in know_true:
return
# a 가 진실을 아는 집합에 소속되어 있다면, b가 소속된 집합을 포함시킴.
if a in know_true:
parents[b] = a
# b 가 진실을 아는 집합에 소속되어 있다면, a가 소속된 집합을 포함시킴.
elif b in know_true:
parents[a] = b
# 루트 노드가 같지 않을 경우, 두 집합을 서로 이어줌.
# 여기서는 노드의 값이 큰 것이 작은 것에 연결되게끔 함.
else:
parents[max(a, b)] = min(a, b)
read = sys.stdin.readline
N, M = map(int, read().split())
know_true = list(map(int, read().split()))[1:]
# 유니온 파인드 연산을 위해, 각 노드 별 루트 노드를 보관하는 list.
parents = list(range(N + 1))
parties = []
for _ in range(M):
peoples, *party = list(map(int, read().split()))
# 해당 파티의 참가자들을 대상으로 Union - Find 진행.
for i in range(peoples - 1):
union(party[i], party[i + 1])
parties.append(party)
result = 0
for party in parties:
for visitor in party:
# 만약 해당 파티의 참가원이 속한 그룹의 루트 노드가 진실을 아는 이라면, 해당 파티 제외.
if find(visitor) in know_true:
break
else:
result += 1
print(result)
하지만 이 문제는 유니온 파인드 라는 개념을 통해서도 접근이 가능했다.
해당 알고리즘을 학습한 후, 이를 토대로 작성한 코드는 상단과 같다.
유니온 파인드의 요지는 서로 연관된 노드를 하나의 트리 (집합) 로 묶어 관리하는데,
추후 두 노드가 같은 집합에 소속되었는지를 find
함수를 통해 체크할 수 있다.
유니온 파인드 관련 문제는 금일 중으로, 혹은 내일까지 2~3문제를 더 풀이할 예정이다.
오늘은 이런 알고리즘 방식도 존재하는구나~ 로 마무리 하려 한다.
https://github.com/RookieAND/BaekJoonCode
지금부터라도 잊었던 감을 다시금 되찾는 노력을 기울여야겠다. 분발하자.