글 읽기 - 1043 거짓말 python 유니온파인드 풀이 틀린 이유를 모르겠어요 고수님들

owenyi3207 2년 전 0

파티마다 최소 값을 가진 부모 노드를 구성원의 부모로 설정하도록 로직을 짰고,
마지막에 파티의 부모가 목격자들의 부모와 같은 경우가 없다면 카운트를 증가하게 했습니다.
틀리는 이유를 알려주실 고수님 계실까요?ㅜ

def find_parent(x):
    if x == 51: return 51
    if parent[x] == x: return x
    parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(nodes):
    _min = 51
    for v in nodes:
        parent_i = find_parent(v)
        if _min > parent_i: _min = parent_i
    party.append(_min)
    for v in nodes:
        parent[v] = _min

N, M = map(int, input().split())
parent = [i for i in range(N + 1)]
party = []
witness = list(map(int, input().split()[1:]))
for _ in range(M):
    union_parent(list(map(int, input().split()[1:])))

for i in range(len(witness)):
    witness[i] = find_parent(witness[i])

cnt = 0
for p in party:
    if find_parent(p) not in witness:
        cnt += 1
print(cnt)

zigui 2년 전 1

14번째 줄에서 parent[v]에 _min을 대입하는 것 대신, parent[find_parent(v)]에 _min을 대입하여야 합니다.

owenyi3207 2년 전 0

감사합니다! parent[find_parent(v)] 말고 parent[parent[v]]로 했습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1043 거짓말 python 유니온파인드 풀이 틀린 이유를 모르겠어요 고수님들

owenyi3207 2년 전 0

zigui 2년 전 1

owenyi3207 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말