[파이썬] 백준 1765 : 닭싸움 팀 정하기 (골드2)

[파이썬] 백준 1765 : 닭싸움 팀 정하기 (골드2)

 

1765번: 닭싸움 팀 정하기

---

문제

 

---

풀이

0. 방향성 생각

친구 관계가 주어지면 항상 같은팀이 되므로 하나로 합치기.

적 관계가 주어지면 어떤 사람 P의 적 E1, E2... ,En에 대해서 모두 합쳐주면 된다.

1. 함수 정의

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,x,y):
    x = find_parent(parent,x)
    y = find_parent(parent,y)
    if x < y:
        parent[y] = x
    else :
        parent[x] = y

재귀적으로 부모를 찾는 find_parent 함수 작성

두 개의 집합을 합칠 때 부모를 찾는 union_parent 함수 작성

 

2. 입력

n = int(input())
m = int(input())
enemy = [[] for i in range(n+1)]
parents = [i for i in range(n+1)]

for _ in range(m):
    relation,a,b = input().split()
    a,b = int(a),int(b)
    if relation == 'F':
        union_parent(parents,a,b)
    else :
        enemy[a].append(b)
        enemy[b].append(a)

친구같은 경우는 그냥 합쳐도 되지만 적의 경우에는 적의 적이 팀이 되므로

사람이 어떤 사람을 적인지 저장하는 enemy 리스트를 작성한다.

3. 출력

for i in range(1,n+1):
    for e1 in range(len(enemy[i])):
        for e2 in range(e1+1,len(enemy[i])):
            union_parent(parents,enemy[i][e1],enemy[i][e2])

answer = set()
for i in range(1,n+1):
    answer.add(find_parent(parents,i))

print(len(answer))

enemy 리스트에 대해서 순회하면서 유니온 파인드 진행

---

전체코드

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,x,y):
    x = find_parent(parent,x)
    y = find_parent(parent,y)
    if x < y:
        parent[y] = x
    else :
        parent[x] = y

n = int(input())
m = int(input())
enemy = [[] for i in range(n+1)]
parents = [i for i in range(n+1)]

for _ in range(m):
    relation,a,b = input().split()
    a,b = int(a),int(b)
    if relation == 'F':
        union_parent(parents,a,b)
    else :
        enemy[a].append(b)
        enemy[b].append(a)

for i in range(1,n+1):
    for e1 in range(len(enemy[i])):
        for e2 in range(e1+1,len(enemy[i])):
            union_parent(parents,enemy[i][e1],enemy[i][e2])

answer = set()
for i in range(1,n+1):
    answer.add(find_parent(parents,i))

print(len(answer))