[백준] 17089. 세 친구 - Python

[Gold V]

 

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

17089번: 세 친구

 

풀이

Brute-Force로 모든 경우를 순회하며 검사하면 되는 문제.

다만 정말 생각없이 3중첩 for문으로 구현한다면, N(3 ≤ N ≤ 4,000) 이기 때문에,

O(N^3) 으로는 시간초과를 받을 수밖에 없다.

 

아래와 같이 순회를 돌게 되면, line 17~20 의 두 번째 for문까지의 시간 복잡도가,

"사람의 수"가 아닌 "친구 관계의 수"의 영향을 받기 때문에, Maximum 약 8000 회의 연산을 한다고 생각할 수 있다.

거기에서 line 25 의 for문까지 포함한다면, 시간 복잡도가 O(N^2) 정도로 수렴함을 알 수 있다.

 

자료구조는 dictionary를 활용하여, value값을 배열로 만들어 graph를 구현하여, 문제를 더욱 쉬이 풀었다.

 

AC.

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

graph = {}
for _ in range(M):
    a, b = map(int, input().split())
    if graph.get(a):
        graph[a].append(b)
    else:
        graph[a] = [b]

    if graph.get(b):
        graph[b].append(a)
    else:
        graph[b] = [a]

result = 10e9
for A in range(1, N+1):
    if not graph.get(A):
        continue
    for B in graph[A]:
        # A - B 는 연결되어 있으므로, graph[A]에 B가 있다면,
        # graph[B]에도 A가 항상 존재한다. 따라서 아래 과정을 거칠 필요가 없다.
        ## if A not in graph[B]:
        ##    continue
        for C in graph[A]:
            if C == B:
                continue
            # 이 조건만 통과하면, A-B-C가 모두 친구인 것.
            if C in graph[B]:
                result = min(result, len(graph[A])+len(graph[B])+len(graph[C])-6)
                
if result == 10e9:
    print(-1)
else:
    print(result)