2 minute read

문제

joowan1108

첫 접근 방법

처음 생각한 알고리즘은 너무 복잡했다.

  1. 파티에 참여한 사람들로 그래프를 구성한 뒤에 진실을 아는 사람들을 시작점으로 하여 bfs를 진행
  2. 연결되어 있다면 연결된 사람들도 진실을 아는 사람이므로 진실을 아는 사람들 list에 추가
  3. 다시 파티에 참여한 사람들 정보로 한명이라도 진실을 아는 사람들 list에 존재한다면 그 party는 count x

–> 한 파티에 참여하는 사람들이 많을 때 graph에 관계를 저장하는게 복잡함

검색하여 구한 방법 1

bfs를 진행하지 않고도 구할 방법을 찾았다. bfs를 굳이 하지 않고

  1. 파티에 참여한 사람들 중에 진실을 아는 사람 (know)집합에 포함되는 사람들이 있다면 나머지 파티원들을 know에 추가 -> 이렇게 party 수만큼 반복하면 서로 관계를 다 집합에 넣을 수 있음
  2. 다시 파티에 참여한 사람들 정보로 한명이라도 진실을 아는 사람들 list에 존재한다면 그 party는 count x

정답 코드 1

import sys
input = sys.stdin.readline

"""

party에서 진실을 아는 사람이 party에 존재한다면 나머지 사람들도 진실을 안다고 볼 수 있으므로
party를 아는 사람 집합에 나머지들도 추가함

"""

n,m = map(int, input().split())
temp = list(map(int, input().split()))
if temp[0]==0:
    print(m)

else:
    know = set()
    for t in temp[1:]:
        know.add(t)

    parties = []
    for _ in range(m):
        party = set(list(map(int, input().split()))[1:])
        parties.append(party)
    
    #순서에 영향받지 않도록 m번 반복
    for _ in range(2):
        for party in parties:
            if party & know:
                know = know.union(party)
    
    ans = 0
    for party in parties:
        if not (party & know):
            ans+=1

    print(ans)

검색하여 구한 방법 2

  1. union find 알고리즘을 통해 party에서 진실을 아는 사람이 존재한다면 나머지 사람들의 부모를 진실을 아는 사람으로 설정
  2. 다시 party 안의 각 사람들에 대해 순회를 돌면서 부모가 진실을 아는 사람 집합 안에 존재한다면 이 party에는 거짓말을 하지 못한다.

정답 코드 2 (분리집합)


import sys
input = sys.stdin.readline

n,m = map(int, input().split())
temp = list(map(int, input().split()))
if temp[0]==0:
    print(m)

else:
    know = set()
    for t in temp[1:]:
        know.add(t)
    
    parents = [i for i in range(n+1)]
    def find(parents, c):
        if parents[c] != c:
            parents[c] = find(parents, parents[c])
        return parents[c]
    

    def union(parents, a, b, know):
        a = find(parents, a)
        b = find(parents, b)
        if a in know and b in know:
            return
        elif a in know:
            parents[b] = a
        elif b in know:
            parents[a] = b
        else:
            if b > a:
                parents[a] = b
            else:
                parents[b] = a

    parties = []
    for _ in range(m):
        party = list(map(int, input().split()))
        party_len = party[0]
        party = party[1:]
        parties.append(party)
        for i in range(party_len-1):
            union(parents, party[i], party[i+1], know)
    
    ans = 0
    for party in parties:
        in_party = False
        for i in range(len(party)):
            if find(parents, party[i]) in know:
                in_party = True

        if not in_party:
            ans+=1
    
    print(ans)

느낀 점

union-find 알고리즘을 이론으로만 알고 있었는데 문제에 실제로 적용하는 것은 처음이라 풀이를 떠올리지 못한 것 같다.

You May Also Enjoy