💡 문제
N명의 사람이 있고, 여기서 세 사람 A, B, C를 고르려고 한다. 세 사람은 모두 친구여야 한다.
세 사람을 고르는 방법은 매우 많이 있을 수 있다. 이때, A의 친구 수 + B의 친구 수 + C의 친구 수가 최소가 되어야 한다. 친구 수의 합을 계산할 때, 세 사람은 빼고 계산해야 한다. 즉, A의 친구 수를 계산할 때, B와 C는 빼고 계산해야 하고, B의 친구 수를 계산할 때는 A와 C, C의 친구 수를 계산할 때는 A와 B를 빼고 계산해야 한다.
입력
첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친구라는 것을 의미한다.
사람은 1번부터 N번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
출력
첫째 줄에 A의 친구 수 + B의 친구 수 + C의 친구 수의 최솟값을 출력한다. 만약, 문제 조건대로 세 사람을 고를 수 없는 경우에는 -1을 출력한다.
💭 접근
이 문제는 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 문제와 굉장히 유사하며, 같이 포함되면 안되는 조합을 뽑는 2422번 문제와 달리 이번 문제에서는 반드시 세 사람이 친구 관계인 조합을 뽑는 문제이다.
따라서 간단한 조합문제로, 세 사람을 뽑을 때 서로가 친구인지 확인하고, 친구 관계가 형성되어 있는 세 사람이 뽑혔다면 이들의 친구들의 수를 센 후, 정답을 갱신해주면 되는 문제이다.
재귀를 활용한 백트래킹 알고리즘을 사용하여서도 해결할 수도 있지만 이런 간단한 조합 문제의 경우 중첩 for문을 사용하여 구현하는 것이 효율적이다.
이 문제에서도 주의해야 할 점으론, 서로 사이에 친구 관계가 형성되어 있는지 확인하기 위해 in 연산을 사용하므로, list 뿐만 아니라 in 연산을 사용하기 위한 set 자료형으로도 친구 관계를 저장해야 한다.
📒 코드 (DFS)
# 간단한 그래프 탐색 문제(DFS)
# 친구를 순차적으로 뽑고, 세명 모두가 친구라면 정답 갱신
# 처음엔 list를 활용한 그래프 하나만 사용해서 in 메서드 사용 시 시간초과(O(N)) 발생
# set을 활용한 그래프를 추가로 선언해서 in 메서드 사용 시 시간초과(O(1)) 방지
# 그리고 친구 수의 합을 구할 때 서로의 관계는 제외해야 하므로 -2한 값을 더함
def dfs(start, depth):
global ans, flag
if depth == 3:
flag = True
cnt = 0
for friend in friends:
cnt += len(graph_list[friend]) - 2
ans = min(ans, cnt)
return
for i in graph_list[start]:
tmp = 0
for friend in friends:
if i in graph_set[friend]:
tmp += 1
if tmp == depth:
friends.append(i)
dfs(i, depth + 1)
friends.pop()
n, m = map(int, input().split())
graph_list = [[] for _ in range(n + 1)]
graph_set = [set() for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
graph_list[a].append(b)
graph_list[b].append(a)
graph_set[a].add(b)
graph_set[b].add(a)
flag = False
ans = float('inf')
for i in range(n):
friends = [i]
dfs(i, 1)
print(ans if flag else -1)
📒 코드 (반복문)
n, m = map(int, input().split())
graph_list = [[] for _ in range(n + 1)]
graph_set = [set() for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
graph_list[a].append(b)
graph_list[b].append(a)
graph_set[a].add(b)
graph_set[b].add(a)
flag = False
ans = float('inf')
for a in range(1, n + 1):
for b in graph_list[a]:
for c in graph_list[b]:
if c in graph_set[a]:
flag = True
cnt = 0
for friend in (a, b, c):
cnt += len(graph_list[friend]) - 2
ans = min(ans, cnt)
print(ans if flag else -1)
💭 후기
집합 자료형을 활용한 간단한 조합 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/17089
