[Python] 1765 닭싸움 팀 정하기

[Gold II] 닭싸움 팀 정하기 - 1765 

[문제 링크](https://www.acmicpc.net/problem/1765)

---

💻 문제 정의

N명의 친구들 중에서, 두 명의 관계가 주어진다. F는 친구, E는 원수이다. M개의 줄에 다음의 정의가 주어지고, 친구끼리는 팀을 이루려고 한다. 이때 다음의 조건으로 팀을 만들 수 있다.

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

즉, 나와 친구가 아니어도 원수의 원수라면 함께 팀을 이룰 수 있다. 이때 가능한 최대 팀 개수를 출력하라.

💡 접근 및 설계

친구 관계를 정의하는 F 리스트와, 원수 관계를 정의하는 E 리스트를 생성한다. E 리스트에는 각 친구마다 누구와 원수 관계인지가 저장된다. 원수 관계가 같다면, 그 둘은 F 리스트에 새롭게 추가한다.

최종적으로 친구 관계가 재정의되었다면, 각 집합의 개수를 출력하면 팀의 개수가 나온다.

✏️ 알고리즘 풀이

F = [[] for _ in range(N+1)]
E = [[] for _ in range(N+1)]
for _ in range(M):
    w, a, b = input().split()

    if w == "F":
        F[int(a)].append(int(b))
        F[int(b)].append(int(a))
    elif w == "E":
        E[int(a)].append(int(b))
        E[int(b)].append(int(a))

F 리스트와 E 리스트를 생성한다.

 

for i in range(1, N+1):
    for j in range(1, N+1):
        if i == j: continue

        if list(set(E[i]) & set(E[j])):
            F[i].append(j)

각 친구들의 원수관계를 비교하며 친구 관계를 새롭게 정의한다. 두 친구의 원수 집합이 있을 때 공통 부분(교집합)이 존재한다면 두 친구는 서로 친구가 될 수 있다.

 

visited = [False] * (N+1)

def bfs(n):
    if visited[n]:
        return 0

    Q = deque()
    Q.append(n)
    visited[n] = True

    while Q:
        c = Q.popleft()

        for ix in F[c]:
            if not visited[ix]:
                visited[ix] = True
                Q.append(ix)

    return 1
  
ans = 0
for i in range(1, N+1):
		ans += bfs(i)

그래프 탐색을 통해 집합의 개수를 센다. 최종적으로 최대 팀 개수를 출력한다.

 

🗒️ 최종 제출 코드

# 1765 닭싸움 팀 정하기

from collections import deque

def bfs(n):
    if visited[n]:
        return 0

    Q = deque()
    Q.append(n)
    visited[n] = True

    while Q:
        c = Q.popleft()

        for ix in F[c]:
            if not visited[ix]:
                visited[ix] = True
                Q.append(ix)

    return 1

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

F = [[] for _ in range(N+1)]
E = [[] for _ in range(N+1)]
for _ in range(M):
    w, a, b = input().split()

    if w == "F":
        F[int(a)].append(int(b))
        F[int(b)].append(int(a))
    elif w == "E":
        E[int(a)].append(int(b))
        E[int(b)].append(int(a))

for i in range(1, N+1):
    for j in range(1, N+1):
        if i == j: continue

        if list(set(E[i]) & set(E[j])):
            F[i].append(j)

visited = [False] * (N+1)

ans = 0
for i in range(1, N+1):
    ans += bfs(i)

print(ans)

 

---

💭 오늘의 회고

-