[백준 3096번] 파이썬 - 영화제

http://www.acmicpc.net/problem/3096

3096번: 영화제

 

 

# 조건

• 강의 왼쪽, 오른쪽에는 N개의 망르이 있고
• 각 마을은 1번부터 N번까지 번호
• 왼쪽 마을 중 하나와 오른쪽 마을 중 하나를 연결하는 배는 총 M개가 있고, 양방향 연걸
• 상근이는 총 4개 마을에서 영화제를 개최하려고 한다.
• 왼쪽 마을에서 2개, 오른쪽 마을에서 2개를 고르며, 왼쪽 마을은 모두 오른쪽 마을과 배로 직접 연결되어 있어야 한다.

영화제를 개최할 마을을 고르는 방법의 수를 구하는 프로그램을 작성하시오.

 

# 접근 방법

• 왼쪽 마을의 번호에 연결된 오른쪽 마을의 번호를 넣어준다.
• 2중 for문을 통해 모든 왼쪽 마을 중 2개를 선택하는 경우의 수를 다 체크해준다.
• 두 마을에 공통으로 연결된 마을을 찾고 선택하는 경우의 수는 1에서 (공통으로 연결된 마을의 수 -1)까지의 합이다.
• 공통으로 연결된 마을의 수를 체크하기 위하여 교집합 &를 이용해주면 된다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

town = [[] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    town[a].append(b)

result = 0
for i in range(1,N+1):
    for j in range(i+1, N+1):
        a = len(set(town[i]) & set(town[j]))
        result += a * (a-1) // 2

print(result)