[코딩테스트][백준] 🔥 백준 18116번 "로봇 조립" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

https://www.acmicpc.net/problem/18116

🕒 Python 풀이시간: 30분

import sys
input=sys.stdin.readline

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

def union_parent(parent,a,b):
    global cnt
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a==b:
        return
    if a<b:
        parent[b]=a
        cnt[a]+=cnt[b]
        cnt[b]=0
    else:
        parent[a]=b
        cnt[b]+=cnt[a]
        cnt[a]=0

parent=dict()
cnt=dict()
n=int(input())
for _ in range(n):
    oper=list(map(str,input().split()))
    if oper[0]=='I':
        if oper[1] not in parent:
            parent[oper[1]]=oper[1]
            cnt[oper[1]]=1
        if oper[2] not in parent:
            parent[oper[2]]=oper[2]
            cnt[oper[2]]=1
        union_parent(parent,oper[1],oper[2])
    else:
        if oper[1] not in parent:
            parent[oper[1]]=oper[1]
            cnt[oper[1]]=1
        print(cnt[find_parent(parent,oper[1])])

로봇 부품 집합 문제! 🤖🔗

로봇 부품의 같은 집합인지의 여부를 따져서 해당 집합에 속하는 갯수를 출력하는 문제이다. union-find라는 것을 한번에 알 수 있었다.

union-find 함수를 정의하고 조합이라는 명령이 주어지면 같은 집합으로 묶고 그렇지 않을 시, 해당 조합의 갯수를 찾아서 출력한다. 그러기 위해 부품이 뭐가 있는지를 일단 확인해야 하는데, 주어진 부품이 초반에 없기 때문에 dict으로 선언하여 새로운 부품이면 갯수와 집합인지를 기록하는 parent에 기록한다.

갯수를 일일이 갯수를 파악해도 되지만 시간초과가 걸리길래 새로 cnt를 일일이 계산하였다. union 연산을 할 때, 부모에 전부 기록하는 형태로 갯수를 부모쪽으로 합쳐주면 해당 부품이 속하는 집합의 부품의 갯수가 나온다.

이렇게 Python으로 백준의 "로봇 조립" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊