python 백준 17089 세 친구

https://www.acmicpc.net/problem/17089

로직

• friends라는 list를 이용하여 친구 관계 정리
  • friends[1] 은 1번과 친구인 사람 목록
  • 목록에는 set 자료 구조 이용 => C라는 사람이 해당 목록에 있는지 조회시 O(1)만에 조회가 가능하므로 list안에 list로 만들 시 메모리 사용 과다 예상
• A와 B와 C가 모두 친구인 경우의 수를 다 찾아야함
• N명의 사람에서 무작위로 3명 고르는 방법 사용시 너무 많은 경우의 수 발생(combination 이용시)
• 그렇기에 A를 고정하고, B를 A 친구목록에서 찾은 후, C를 B 친구목록에서 찾는 방법 사용
  • 이 때 C와 A가 친구가 아닐 수 있으므로 여부 확인

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
friends = [set() for i in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    friends[a].add(b)
    friends[b].add(a)

maxNum = 12000
ans = maxNum
for A in range(1,N+1):
    for B in friends[A]:
        for C in friends[B]:
            if C in friends[A]:
                ans = min(ans,len(friends[A]) + len(friends[B]) + len(friends[C]) - 6)
if ans != maxNum:
    print(ans)
else:
    print(-1)