백준: 17089 세 친구

문제

17089번: 세 친구

 

문제 풀이

 문제에서는 N명의 사람이 있고, 세 사람을 선택할 때 세 사람이 모두 친구이고 세 사람의 친구 수의 합이 최소가 되는 경우를 찾아 반환하여야 한다. 문제의 조건에는 세 사람을 선택할 경우 세 사람은 친구에서 제외해야 한다는 조건이 있다. 처음에는 문제를 `DFS`를 통해 접근해야 하지 않나 라고 생각하였는데 세 사람을 선택하는 것을 `3중 반복문`을 통해 경우를 탐색하면 시간 초과가 발생하지 않고 문제를 해결할 수 있다.

 

코드

from sys import stdin
from math import inf


if __name__ == '__main__':
    answer = inf
    n, m = map(int, stdin.readline().split())
    relation = [[False] * (n + 1) for _ in range(n + 1)]
    friends = [0] * (n + 1)

    # 친구 관계와 친구 수를 저장함.
    for i in range(m):
        me, my_friend = map(int, stdin.readline().split())
        relation[me][my_friend] = True
        relation[my_friend][me] = True
        friends[me] += 1
        friends[my_friend] += 1

    # 3중 for 문으로 친구 세 명을 선택하여 탐색.
    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            # 첫번째 친구 만족.
            if relation[i][j]:
                for k in range(j + 1, n + 1):
                    # 두번째, 세번째 친구 만족
                    if relation[i][k] and relation[j][k]:
                        # [B, C], [A, C], [A, B]와 같이 연결된 친구 6명을 제외해야 함.
                        answer = min(answer, friends[i] + friends[j] + friends[k] - 6)

    print(-1 if answer == inf else answer)