글 읽기 - 파이썬) 유니온 파인드의 함수를 바꾸면 출력초과가 뜹니다.

boorooksus 4년 전 1

출력 초과가 뜨는 이유를 모르겠습니다.

아래 코드는 유니온파인드를 이용하여 같은 네트워크 속 친구 수를 찾도록 만든 것 입니다.

여기서 부모를 합치는 함수는 9~20번째 줄의 unionParent1(a, b)과 22~28번째 줄의 unionParent2(a,b) 두 가지로 만들어 보았습니다. 두 함수 모두 잘 작동이 됩니다. 그런데 unionParent2 함수를 이용할 경우 맞다고 채점이 되지만 unionParent1함수를 이용할 경우 출력 초과가 뜹니다.

unionParent1의 함수는 입력받은 a, b 중에 더 작은 쪽의 부모로 합치는 것이고

unionParent2의 함수는 a가 b의 부모인 것을 전제로 두고 실행하는 함수입니다.

두 경우 모두 잘 작동되는것 같은데 왜 전자의 경우 출력초과가 뜨는지 궁금합니다.

감사합니다.

from sys import stdin

def getParent(x):
    if parent_dict[x] == x:
        return x
    parent_dict[x] = getParent(parent_dict[x])
    return parent_dict[x]

def unionParent1(a, b):
    a = getParent(a)
    b = getParent(b)
    sum = cnt_dict[a] + cnt_dict[b]
    cnt_dict[a] = sum
    cnt_dict[b] = sum
    #더 작은 쪽을 부모로 갖는다
    if a > b:
        parent_dict[a] = b
    else:
        parent_dict[b] = a
    return

def unionParent2(a, b): #a가 b의 부모인 것을 전제로 할 때
    a = getParent(a)
    b = getParent(b)
    if a != b:
        parent_dict[b] = a
        cnt_dict[a] += cnt_dict[b]
    return

t = int(stdin.readline()) #number of test cases
for i in range(t):
    f = int(stdin.readline()) #number of friendships formed
    #부모를 저장하는 딕셔너리와 같은 네트워크 친구 수를 저장하는 딕셔너리
    parent_dict, cnt_dict = dict(), dict()
    for j in range(f):
        name1, name2 = stdin.readline().split()
        #입력받은 이름이 딕셔너리에 없는 경우 저장
        if name1 not in parent_dict:
            parent_dict[name1] = name1
            cnt_dict[name1] = 1
        if name2 not in parent_dict:
            parent_dict[name2] = name2
            cnt_dict[name2] = 1
        #부모를 합친다
        unionParent2(name1, name2)
        #unionParent1(name1, name2) 이 함수를 이용하면 출력초과가 뜬다

        #같은 네트워크의 친구 수를 출력
        print(cnt_dict[getParent(name1)])

djm03178 4년 전 4

https://ideone.com/HCAhHz

wjdclgns12 4년 전 1

위 함수는 a b가 이미 같은 집합에 있어도 또 합칩니다

boorooksus 4년 전 0

말씀대로 중복으로 카운트 돼서 안되던것이었네요.

아래와 같이 수정하니 잘 됩니다.

def unionParent1(a, b):
    a = getParent(a)
    b = getParent(b)
    sum = cnt_dict[a] + cnt_dict[b]
    #더 작은 쪽을 부모로 갖는다
    if a > b:
        parent_dict[a] = b
        cnt_dict[a] = sum
        cnt_dict[b] = cnt_dict[a]
    elif a < b:
        parent_dict[b] = a
        cnt_dict[b] = sum
        cnt_dict[a] = cnt_dict[b]
    return

감사합니다! 좋은 하루 되세요

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

문제

문제

출처

ICPC

파이썬) 유니온 파인드의 함수를 바꾸면 출력초과가 뜹니다.

boorooksus 4년 전 1

djm03178 4년 전 4

wjdclgns12 4년 전 1

boorooksus 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말