[백준][Python] 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

 

 

코드

from collections import defaultdict
import sys

n,m = map(int,input().split())
cnt = 0
dic = defaultdict(list)
for _ in range(m):
	a,b = map(int,sys.stdin.readline().split())
	dic[a].append(b)
	dic[b].append(a)
for i in range(1,n+1):
	for j in range(i+1,n+1):
		flag = 0
		if j in dic[i]:
			flag = 1
		for k in range(j+1,n+1):
			if flag == 0 and k not in dic[i] and k not in dic[j]:
				cnt+=1
		
print(cnt)

 

설명

만약 섞어먹으면 안되는 조합이 1,2로 주어졌다면 딕셔너리에 {1:[2], 2:[1]} 와 같은 식으로 저장을 해주었다.

for문을 써서 완전 탐색을 하면서 섞어먹으면 안되는 조합이 없는 경우에 cnt 값을 증가시켜줬다.