[BOJ / 백준] 17089번 세 친구 성공 파이썬(Python) 문제 풀이

 

문제

 

문제 링크 : https://www.acmicpc.net/problem/17089

17089번: 세 친구

 

 

 

 

 

CODE

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
frd = [[False for _ in range(n)] for _ in range(n)]     # 친구 여부
cnt = [0 for _ in range(n)]                             # 친구 수
for i in range(m):
    i1, i2 = map(int, input().split())
    frd[i1 - 1][i2 - 1] = True
    frd[i2 - 1][i1 - 1] = True
    cnt[i1 - 1] += 1
    cnt[i2 - 1] += 1
result = 12001

for i in range(n):
    for j in range(i + 1, n):
        if not frd[i][j]:                       # A와 B가 친구가 아닌 경우
            continue
        for k in range(j + 1, n):
            if not frd[i][k] or not frd[j][k]:  # A와 C 또는 B와 C가 친구가 아닌 경우
                continue
            result = min(result, cnt[i] + cnt[j] + cnt[k] - 6)

if result == 12001:
    print(-1)
else:
    print(result)

 

 

 

 

풀이

💡 idea

- n명 중 세 명을 뽑는 경우를 모두 고려한다

- 세 명이 서로 친구인지 검사한 뒤 이전에 저장한 result 보다 작다면 저장한다

 

 

💡 implementation

- 친구 수를 저장할 때마다 frd에서 친구 수를 세는 과정을 생략하기 위해 cnt 리스트에 각 사람의 친구 수를 저장

- frd[i][j] == True이면, i와 j가 친구임을 나타낸다. 따라서 False인 경우 친구가 아니기 때문에 해당 경우를 건너뛴다

if not frd[i][j]:
            continue

 

 

 

 

 

 

 

결과