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

시간 제한 1초, 메모리 제한 128MB

# 조건

• 한윤정과 친구들은 이탈리아로 방학 여행을 갔다.
• 이탈리아는 덥다.
• 윤정이와 친구들은 아이스크림을 사먹기로 했다.
• 아이스크림 가게에는 N종류의 아이스크림이 있다.
• 모든 아이스크림은 1부터 N까지 번호가 매겨져있다.
• 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다.
• 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다.
• 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

입력

• 첫째 줄에 정수 N과 M이 주어진다.
• N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다.
• 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다.
• 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

출력

• 첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

# 접근 방법

• 딕셔너리와 조합을 이용해준다.
• 입력받는 섞어 먹으면 안되는 조합을 딕셔너리에 기록해준다.
• 이후 combination을 사용하여 주어진 N을 3개씩 조합하여 각 조합이 서로 기록되어 있는지 체크해주고 3개 모두 True를 반환한다면 result += 1을 해준다.

import sys  
sys.stdin = open('input.txt')  
si = sys.stdin.readline  
from collections import defaultdict  
from itertools import combinations  

def can(v1, v2, v3):  
    if not v1 in check[v2] and not v1 in check[v3]:  
        return True  
    return False  
N, M = map(int, si().split())  
check = defaultdict(list)  
for _ in range(M):  
    a, b = map(int, si().split())  
    if a > b:  
        a, b = b, a  
    check[a].append(b)  

result = 0  
for q1, q2, q3 in combinations(range(1, N+1), 3):  
    if can(q1, q2, q3) and can(q2, q1, q3) and can(q3, q1, q2):  
        result += 1  
print(result)

• 다만, 모든 조합에서 모든 경우를 체크하는 것은 시간적으로 효율적이지 못하다.
• 따라서 3개의 반복문을 통해 현재 숫자가 이미 맛없는 조합에 기록되어있다면 바로 continue해준다.
• 나의 코드는 defaultdict을 이용하여 기록해주었지만
• 2차원 list를 활용하여 체크해놓는 경우 시간을 더 줄일 수 있다.

import sys  
sys.stdin = open('input.txt')  
si = sys.stdin.readline  
from collections import defaultdict  

N, M = map(int, si().split())  
check = defaultdict(list)  
for _ in range(M):  
    a, b = map(int, si().split())  
    if a > b:  
        a, b = b, a  
    check[a].append(b)  

result = 0  
for i in range(1, N+1):  
    for j in range(i+1, N+1):  
        if j in check[i]:  
            continue  
        for k in range(j+1, N+1):  
            if not k in check[i] and not k in check[j]:  
                result += 1  
print(result)

• 위에가 3중 반복문
• 아래가 combination