[백준][파이썬] 17089 - 세 친구

문제 번호 : 17089번 세 친구
문제 출처 : https://www.acmicpc.net/problem/17089

Code

import sys

n, m = map(int, input().split())
relations = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

friends = [set() for _ in range(n)]
for relation in relations:
    friends[relation[0]-1].add(relation[1])
    friends[relation[1]-1].add(relation[0])

num_friends = m
for a in range(n):
    for b in friends[a]:
        for c in friends[b-1]:
            if c in friends[a]:
                num_friends = min(num_friends, len(friends[a]) + len(friends[b-1]) + len(friends[c-1]) - 6)
if num_friends < m:                
    print(num_friends)
else:
    print(-1)

Idea

1. 입력된 친구가 모두 A, B, C의 친구인 경우 세 친구의 친구 수 합의 최대는 m - 6이다.
2. A를 정하고 B는 A의 친구 중 한명이고 C는 B의 친구이면서 A의 친구인 경우에서 친구 수의 최소값을 찾아낸다.
3. b > a, c > b 조건을 넣은 이유는 먼저 순회한 조합을 순회하지 않기 위함이다. 이 두 조건이 없다면 순열처럼 동작할 것이지만 이 조건으로 인해서 조합이 되어서 시간 복잡도가 줄어든다. 이 조건 두 줄만으로 1880ms에서 92ms로 시간이 확 줄었다.