[BOJ/python]1765번 닭싸움 팀 정하기

백준 1765번 닭싸움 팀 정하기 파이썬

문제 링크 - https://www.acmicpc.net/problem/1765

1765번: 닭싸움 팀 정하기

union-find 문제는 해당 카테고리의 문제라는 것을 알고 있다면 쉽게 풀 수 있다. 하지만 문제를 보고 union-find로 풀어야겠다는 아이디어를 떠올리는 것은 어려울 수 있다. 팀을 만들어야 되는 문제이고 팀의 개수를 물어보았기 때문에 union-find로 풀면 될 것 같았다.

1. 풀이

• 팀을 만들기 위해 친구는 입력값을 받을 때 모두 union 한다.
• 원수인 경우 인접 리스트를 통해 서로 원수 관계인 것을 표현한다.
• 모든 학생을 탐색하며 원수 배열의 길이가 2 이상인 경우 해당 배열에 있는 학생들을 union해서 팀으로 만들어준다.

2. 코드

#닭싸움 팀 정하기union find
def find(u):
    if p[u] <0 : 
        return u
    p[u] = find(p[u])
    return p[u]

def union(u,v) :
    u=find(u)
    v=find(v)
    if u==v :
        return
    
    if abs(p[u]) >= abs(p[v]):
        p[u]+=p[v]
        p[v]=u
    
    else:
        p[v]+=p[u]
        p[u]=v
    
N= int(input())
p = [-1 for _ in range(N+1)]
e = [[] for _ in range(N+1)]
M = int(input())

for i in range(M):
    r, a, b = input().split()
    a,b = int(a), int(b)
    if r=='F' :
        union(a,b)
    else:
        e[a].append(b)
        e[b].append(a)

for i in range(1, N+1):        #각 학생들의 원수 배열을 탐색하며, 원수가 2명 이상이면 그 원수끼리 모두 팀으로 만들기 
    if len(e[i]) > 1:
        for j in range(1, len(e[i])):
            union(e[i][j-1], e[i][j])
    
sol=0
for i in range(1, N+1):
    if p[i]<0:
        sol+=1
print(sol)