[백준/1765] 닭싸움 팀 정하기 (Python)

Problem : https://www.acmicpc.net/problem/1765

1765번: 닭싸움 팀 정하기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:40:02

 

---

 

문제 설명

 

닭싸움은 월드의 전통이다. 이번 캠프에서도 어김없이 닭싸움 대회가 열렸다. 그런데, 닭싸움을 하기 위해서는 반드시 누가 우리 편이고, 누가 우리 편이 아닌지를 알아야 할 것이다. 닭싸움의 팀을 정하는 원칙은, 평소 학생들의 인간관계에 따라 다음과 같이 정리할 수 있다.

1. 내 친구의 친구는 내 친구이다.
2. 내 원수의 원수도 내 친구이다.

 

이 때 두 학생이 친구이면 같은 팀에 속해있어야 하며, 같은 팀에 속해 있는 사람들끼리는 전부 친구여야 한다.

학생들의 인간관계가 주어지면, 닭싸움을 위한 팀 정하기를 할 때, 최대 얼마나 많은 팀이 만들어질 수 있는지 알아내는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

첫째 줄에 학생의 수 n이 주어진다. 각 학생들은 1부터 n까지 번호가 매겨져 있다. (2 ≤ n ≤ 1000) 

둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (1 ≤ m ≤ 5000)

다음 m개의 줄에는 한 줄에 한 개씩, 학생 간의 인간관계가 F p q 혹은 E p q의 형태로 공백으로 구분되어 주어진다. (1 ≤ p < q ≤ n)

첫 번째 글자가 F인 경우에는 p와 q가 친구인 것이고, E인 경우는 p와 q가 원수인 경우이다. 

입력은 모순이 없음이 보장된다. 즉, 두 학생이 동시에 친구이면서 원수인 경우는 없다.

 

출력

첫째 줄에, 가능한 최대 팀 개수를 출력한다

 

입력 예시

6
4
E 1 4
F 3 5
F 4 6
E 1 2

 

출력 예시

3

 

 

---

 

풀이

 

나와 같은 경우는  유니온-파인드 기법을 이용해서 풀었다. 첫 번째 시도같은 경우는 플로이드-와셜 알고리즘까지 조합(즉 모든 친구인 경우를 구하고 시작)해보았지만, 이 경우는 O(N^3)의 벽을 넘지 못하고 시간초과를 일으킨다...

 

핵심은 간단하다. 두 사람이 서로 친구라면, 둘의 parent를 같게 하면 된다. 이 경우는 주어진 대로

 

• 원수의 원수 : 저장된 두 사람이 공통의 원수를 가지고 있다면, 그 둘은 친구이다. 즉 enemy인 경우만을 따로 지정하여 모든 임의의 두 친구간에 공통의 원수를 찾아보면 된다. 이는 O(N^2)이 소요된다.
• 친구의 친구 : 이 경우 입력받자마자 바로 Union하면 된다. O(1)이 소요된다.

모든 친구인 경우를 구하지 않더라도, 최종적으로는 parent에 최소 친구 집합의 경우의 수가 전부 저장될것이다. 즉 이 parent의 경우를 count해주면 된다.

 

 

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

parent = list(range(N))

def find(a) :
  if a == parent[a] :
    return a
  parent[a] = find(parent[a])
  return parent[a]

def union(a, b) :
  pa = find(a)
  pb = find(b)

  if pa <= pb :
    parent[pb] = pa
  else :
    parent[pa] = pb

def init() :
  enemy_adj_dict = { key : list() for key in range(N) }

  for _ in range(M) :
    typ, p, q = input().split()
    p, q = int(p)-1, int(q)-1

    if typ == 'F' :
        union(p, q)
    else :
        enemy_adj_dict[p].append(q)
        enemy_adj_dict[q].append(p)
  return enemy_adj_dict

def ismatch(a, b, adj_dict) :
    for i in adj_dict[a] :
        for j in adj_dict[b] :
            if i == j :
                return True

    return False
    
def full_search(adj_dict) :
  for i in range(N-1) :
    for j in range(i+1, N) :
      if parent[i] != parent[j] and ismatch(i, j, adj_dict):
        union(i, j)

  for i in range(N) :
    find(i)

  print(len(set(parent)))

def solve() :
  adj_dict = init()
  full_search(adj_dict)

solve()

풀이 완료~

p.s. 그래프 이론 혹은 DFS등을 통해서 풀 수도 있을 것 같다.