[BOJ] 17089번 - 세 친구

완전탐색 문제들을 볼 때마다 시간초과로 고생했던 것 같다. 2020년도 카카오 '외벽점검'이란 문제 역시 완전탐색 문제로 풀었을 때,

시간을 어떻게 줄여야 하는 지 몰라 해설을 봤던 것 같다. 카카오 문제 만큼은 그냥 풀고싶었는데,, 더 이상 시간 뺏길 순 없어 봤다.

 

시간이 날 때마다 문제들을 하나씩 풀어보는데, 여전히 감도 안 잡히는 문제들이 많고 어떻게 접근해야할 지 모르는 문제들이많다.

많은 유형들을 여러번 풀어보고, 숙달이 된다면 문제를 보는 눈이 조금은 달라지지 않을까 생각이든다.

 

www.acmicpc.net/problem/17089

17089번: 세 친구

문제를 봤을 때 간단한 로직이 생각났다.

 

1.  친구 3명고르기

2. 고른 친구 3명이 서로 친구인지 확인하기

3. 만약 친구라면 answer 값 업데이트로

 

매우 간단하게 로직이 생각났기 때문에 빠른 시간 내 짰지만, 보기 좋게 시간초과가 났다.

from sys import stdin
from collections import deque

std = stdin.readline

N, M = map(int, std().split())
friend = [[]for i in range(N)]

for i in range(M):
    a, b = map(int, std().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

check = [0 for i in range(N)]
fr = []
answer = 20000


def is_friend(i, j, k):
    cnt = 0
    for f in friend[fr[i]]:
        if f in [fr[j], fr[k]]:
            cnt += 1
    if cnt == 2:
        return True
    return False


def dfs(start, depth):
    global answer
    if depth == 3:
        # 세 사람이 친구인지 확인
        flag = False
        if [is_friend(0, 1, 2), is_friend(1, 0, 2)] == [True, True]:
            flag = True

        friend_sum = 0
        if flag:
            for f in fr:
                friend_sum += len(friend[f])-2
        else:
            return

        if friend_sum < answer:
            answer = friend_sum
        return

    for i in range(start, N):
        if check[i] == 0:
            check[i] == 1
            fr.append(i)
            dfs(i+1, depth+1)
            fr.pop()
            check[i] = 0


dfs(0, 0)
print(answer if answer != 20000 else -1)

 

시간초과의 이유가 뭘까? 하고 처음부터 생각해봤다...  첫번째 접근인 친구 3명 고르기에 그 이유가 있다는 것을 알았다.

4000명의 친구가 존재할 때 3명을 선택하는 방법의 가지수는 4000*3999*3998/6 으로 10억정도는 나온다는 것을 알 수 있다.

최소 10초이상 걸린다고 생각한다고 보면 시간초과는 당연한 것 같다.

 

그래서 3명을 고르는 방법을 어떻게 줄일지 생각해봤다. 4000명에서 2명을 고르는 방법은 1600만 정도로 충분히 가능 할 순 있다.

문제에서 친구관계의 수도 4000번으로 줄여줬기 때문에 가능했다.

 

친구들의 저장 리스트

여기서 중요한 것은 1번친구들의 리스트를 본 뒤 2명을 택할 때 그 친구들이 서로 친구인지 확인하는 방법이다.

1번이 B,C 를 선택했다고 하자. 이미 1번과 B, 1번과 C는 친구이다. 물론 역도 성립한다.

여기서 하나의 조건만 더 보면 된다. 만약 B와 C가 친구인지만 확인하면 되는 것이다. 

이렇게 친구를 확인해주고 각각의 친구들의 수의 최소를 생각해주면 답을 구할 수 있다.

 

from sys import stdin
from itertools import combinations
from collections import deque

std = stdin.readline

N, M = map(int, std().split())
friend = [[]for i in range(N)]
answer = 20000
for i in range(M):
    a, b = map(int, std().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

for i in range(N):
    if len(friend[i]) < 2:
        continue
    A = friend[i]
    for fr in combinations(A, 2):
        B, C = fr
        friend_sum = 0
        if C in friend[B]:
            friend_sum = len(A)+len(friend[B])+len(friend[C]) - 6
            if friend_sum < answer:
                answer = friend_sum

print(answer if answer != 20000 else -1)

combinations을 쓰니 코드가 줄어들었다. 1600만의 리스트를 만들었다 가정했을 때 MB 수는 16MB 정도 밖에 안되어 이렇게 구현했다.