[알고리즘] 28일차 (거짓말쟁이가 되긴 싫어) #백준1043번

📌 문제 052) 거짓말쟁이가 되긴 싫어

시간 제한 2초, 골드 IV, 백준 1043번

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

4 3 # 사람 수, 파티 수
0 # 진실을 아는 사람 정보
2 1 2 # 파티 정보
1 3
3 2 3 4

출력

첫째 줄에 문제의 정답을 출력한다.

3

1단계 문제 분석

• 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각가의 파티마다 union 연산을 이용해 사람들을 연결한다. 이 작업을 하면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 바라보게 된다.
• 이후, 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인함으로써 과장된 이야기를 할 수 있는지 판단할 수 있다.

1. 진실을 아는 사람 데이터, 파티 데이터, 유니온 파인드를 위한 대표 노드 자료구조를 초기화한다.
2. union 연산을 수행해 각 파티에 참여한 사람들을 1개의 그룹으로 만든다.
3. find 연산을 수행해 각 파티의 대표 노드와 진실을 아는 사람들이 같은 그룹에 있는지 확인한다. 파티 사람 노드는 모두 연결돼 있으므로 아무 사람이나 지정해 find 연산을 수행한다.
4. 모든 파티에 관해 3번 과정을 반복 수행하고, 모든 파티의 대표 노드가 진실을 아는 사람들과 다른 그룹에 있다면 결괏값을 증가시킨다.

2단계 슈도 코드

N(사람 수) M(파티 개수)
trueP(진실을 아는 사람 데이터)
T(진실을 아는 사람 수)
party(파티 데이터)

# find 연산
find(a):
	a가 대표 노드면 리턴
    아니면 a의 대표 노드 값을 find(parent[a]) 값으로 저장 - 재귀 함수 형태

# union 연산
union(a, b):
	a와 b의 대표 노드 찾기
    두 원소의 대표 노드끼리 연결

# checkSame -> 두 원소가 같은 집합인지 확인
checkSame(a, b):
	a와 b의 대표 노드 찾기
    두 대표 노드가 같으면 true
    아니면 false return

파티 데이터 저장

for N만큼 반복:
	대표 노드를 자기 자신으로 초기화

for M만큼 반복:
	firstPeople(i번째 파티의 1번째 사람)
    for j를 i번째 파티의 사람 수만큼 반복:
    	union(firstPeople, j) # 각 파티에 참여한 사람들을 1개의 그룹으로 만들기

for M만큼 반복:
	firstPeople(i번째 파티의 사람)
    for j -> 진실을 아는 사람들의 수만큼 반복:
    	# 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장할 수 없음
        find(firstPeople), find(trueP[j]) 비교
    모두 다른 경우 결괏값 1 증가

결괏값 출력

3단계 코드 구현

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)

• del party[i][0] 하는 이유 는 각 파티 리스트에서 첫 번째 요소를 제거하여 각 파티의 대표 노드를 설정하고, 대표 노드를 기준으로 파티 참가자들을 그룹화하는 데 사용된다.
• del party[i][0]를 사용하면, party[i][0]에 저장된 데이터가 삭제되고, party[i][1]이 이전 데이터를 대신하게 된다. 이 작업은 파티의 대표 노드를 설정하기 위해 첫 번째 요소를 삭제하고 대표 노드를 정의하는 데 사용된다.