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

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

17089번: 세 친구

Problem

• N명의 사람이 있고, 여기서 세 사람 A, B, C를 고르려고 한다.

조건

• 세 사람은 모두 친구여야 한다.
• A의 친구 수 + B의 친구 수 + C의 친구 수가 최소가 되어야 한다. 친구 수의 합을 계산할 때, 세 사람은 빼고 계산해야 한다.
• 즉, A의 친구 수를 계산할 때, B와 C는 빼고 계산해야 하고, B의 친구 수를 계산할 때는 A와 C, C의 친구 수를 계산할 때는 A와 B를 빼고 계산해야 한다.
• 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친구라는 것을 의미한다.
• 사람은 1번부터 N번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
• 만약, 문제 조건대로 세 사람을 고를 수 없는 경우에는 -1을 출력한다.

SOL

세 사람이 모두 친구인 경우의 수 중에서, A의 친구의 수 , B의 친구의 수, C의 친구의 수가 최소가 되는 경우를 찾는 문제이다. 간단한 문제처럼 보이지만, 여기에는 엄청난 개념이 또 들어있는 문제이다.. (ㄷㄷ..)

 

완전탐색

 

세 사람이 친구인 경우의 수는 여러가지 방법으로 구해줄 수 있다.

 

1. 그래프 탐색으로 세사람의 사이클 여부를 확인해주기.
   • 좋은 방법이다. 사이클을 형성하는 3가지 노드를 모두 알아야 하기 때문에, 사이클이 있는지 없는지 확인 후, 사이클을 형성하는 3가지 노드를 가지고, 친구의 수를 세어줘야한다.
2. 모든 경우를 골라줄려면, 삼중반복을 해주기.
   • 첫번째 노드 선택 -> 남은 노드중 1개 선택 -> 남은 노드중 1개 선택으로 완전 탐색으로 하는 방법 =>4000^3 TL 발생.
   •  첫번째 노드 선택 -> 남은 노드중 1개선택 -> 선택한 노드가 친구 관계인지 확인 => 친구 관계라면, 남은 노드 중 1개를 선택 => 친구 관계 확인 => 최소의 친구수 반영 
3. combination으로 N개의 노드중 3개를 뽑는 경우의수를 모두 구해주기.
   • 4000C3 => 10억가지다. 안된다.

아래의 코드부터 먼저 보자. 이 코드의 시간복잡도가 O(N^3) 일까?

언뜻보면 , 3중반복이라서 , O(N^3) 처럼 보인다. 하지만, if adj[i][j] 인 경우에만, 삼중반복을 돌게된다.

• adj[i][j]가 하나도 없다면, N^2 이고,  adj[i][j]는 최대 M개 이므로, O(N)*O(N+M)이 되버린다.

즉, O(N^2)이되므로, TL을 통과 가능하게 되버리는 거다.

 

삼중반복이라고, 다 같은 삼중반복이 아니다. 조건을 걸어서, 반복을 통제해준다면, 반복의 횟수를 줄일 수 있게 된다. 

 

#세명 모두 친구 여야한다.
import sys

input= sys.stdin.readline
N,M=map(int,input().split())
adj=[[0 for _ in range(N+1)] for _ in range(N+1)]
friends=[0 for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    adj[a][b]=1
    adj[b][a]=1
    friends[a] +=1
    friends[b] +=1
ans=sys.maxsize
for i in range(N+1):
    for j in range(i+1,N+1):
        # i,j가 친구
        if adj[i][j]:
            for k in range(j+1,N+1):
                if adj[i][k] and adj[j][k]:
                    ans = min(ans,friends[i]+friends[j]+friends[k] -6)
                    
print(-1 if ans ==sys.maxsize else ans)