글 읽기 - 서로소 집합 코드의 find_parent 관련 질문입니다!!!

plastica99 3년 전 0

제 코드에서 주석처리한 "1번" 코드는 정답이고 "2번" 코드는 오답인 이유가 뭘까요?

LIMIT = 100003
import sys
sys.setrecursionlimit(LIMIT)

G = int( input() )
P = int( input() )
a = []
for _ in range(P):
    a.append( int(sys.stdin.readline().rstrip()) )


def find_root(root, x):
    if root[x] != x:
        root[x] = find_root(root, root[x])
    return root[x]

def union(root, x, y):
    rx = find_root(root, x)
    ry = find_root(root, y)
    if rx < ry:
        root[ry] = rx
    else:
        root[rx] = ry
    # 1번 코드와 2번 코드의 차이를 없앨 수 있다고 생각한 코드
    dummy = find_root(root, x)
    dummy = find_root(root, y)
        
# root는 g 번째 이하의 게이트 중 다음으로 비행기를 도킹시 킬 게이트 번호를 의미한다.
root = [ i for i in range(G+1) ]
answer = 0
for cnt, g in enumerate(a):
    # 다음으로 도킹시킬 게이트번호가 1 이하인 경우 자리가 없는 것이므로 루프를 종료하고 여태 도킹한 비행기 수를 출력
    # if find_root(root, g) == 0:  # 1번
    # if root[g] == 0:             # 2번
        break
    union(root, root[g] - 1, g)
    answer += 1

print(answer)

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

문제

문제

출처

ICPC

서로소 집합 코드의 find_parent 관련 질문입니다!!!

plastica99 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말