[백준] #17089 - 세 친구

2023/7/14-15

골드5

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

17089번: 세 친구

 

 

🔎 분석

생각보다 단순했던 문제.

문제를 보자마자 여러 명 중에서 3명의 친구를 골라야 한다고 생각해서 조합을 사용해야겠다고 생각했다. 그리고 조합을 사용해서 빠르게 풀었다. 예제가 모두 돌아가서 제출했지만, 계속해서 메모리 초과가 나왔다. 연속해서 시간초과랑 메모리 초과가 뜨니까 이래서 어려운거구나 .. 하는 생각이 들었다.

 

어떻게 해결할까 고민했는데, 친구관계를 담은 이차원 배열도 생성하고 조합을 적용한 결과 배열도 사용해서 사람 4000명에 친구관계도 4000개나 나올 수 있기 때문에 메모리가 과하게 사용되었다는 생각이 들었다. 그래서 조합 결과를 배열에 담지 않는 방법, 사용한 배열을 다시 사용하는 방법 등을 고민했는데, 조합을 한다는 것 자체가 너무 경우의 수가 많아진다고 생각되어 조합을 포기했다.

for문을 사용하는 방식으로 수정하였더니 해결되었다. 과정은 아래와 같다.

 

✏️ 과정

조합을 안 쓰고 생각해보면 그냥 각 개인의 친구관계에 속한 사람의 친구관계에 자신이 포함되는지 확인하는 방식으로 해결할 수 있는 문제였다.

그래서

1. 이중 for문을 사용해서 자신의 친구 목록에 속한 사람의 친구관계에 자신이 포함되는지 확인 (index로)

• check1 = 첫 번째 for문은 내 목록에 속하는 j의 친구 목록에 자신이 포함되는지 여부
• check2 = 두 번째 for문은 내 목록에 속하는 k의 친구 목록에 자신이 포함되는지 여부
• check3 = j, k가 서로의 친구 목록에 서로가 포함되는지 여부
• check0 = check1 and check2 and check3

2. 서로 모두 친구인 3명이 확정되면 (check0==True) 각 개인의 친구 수를 모두 더하고 서로를 빼준다 (3명의 친구수 총합 - 2*3)

3. 이렇게 구한 값이 min값인지 확인해주고, min값을 업데이트 해준다.

4. min이 초기 설정값 그대로면 -1 출력, 제대로 바뀐 min값이면 min 출력 이렇게 구현을 했다.

 

제출한 결과 맞았습니다가 나왔다. 근데 시간이 2464ms.. 그래서 줄일 방법을 생각해봤고, 앞서 구현한 것처럼 하나하나에 들어가서 친구 목록에 포함되는지 확인할 필요 없이, for문 자체를 해당 친구의 친구 목록에서 돌리면 되는 것이었다.

컨셉은 처음 방법과 같은데,

1. 세 친구를 선택할 때

• 첫 번째 for문은 내 친구 목록에 속하는 j
• 두 번째 for문은 j의 친구 목록에 속하는 k
• k가 내 친구 목록에 있는지 확인

⇒ 이렇게만 해주면 j는 내 친구, j-k는 친구, k는 내 친구

 

2, 3, 4는 동일하게 해주면 된다.

 

 

📍TIP

이런 식으로 바꿔주니까 코드 길이도 줄어들고, 시간도 반토막이 나왔다. 1420ms.

입력도 readline으로 바꿔주니까 1152ms로 줄었다.

 

 

💻 코드

from itertools import combinations
import sys

input = sys.stdin.readline

# 친구 정보 세팅
N, M = map(int, input().split())
friends_num_list = [[] for _ in range(N)]

for _ in range(M):
    num1, num2 = map(int, input().split())
    friends_num_list[num1-1].append(num2-1)
    friends_num_list[num2-1].append(num1-1)

num_min = 4000

for friends_list in friends_num_list:
    # 셋이 모두 친구인 경우 찾기
    for j in friends_list:    
        for k in friends_num_list[j]:
            if k in friends_list:
                # 셋이 모두 친구라면, 해당 경우의 전체 친구 수 구하기 - 서로
                num = len(friends_list)+len(friends_num_list[j])+len(friends_num_list[k])
                num -= 2*3
                if num < num_min:
                    num_min = num    
            
            
if num_min == 4000:
    print(-1)
else: print(num_min)