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

문제를 요약해보자.

 

아이스크림 종류의 개수 : N개 

섞으면 안되는 조합의 개수 : M개

 

섞으면 안되는 조합을 피해서, 3가지를 선택하면 된다.

 

 

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

dp = [0] * (n + 1)
dic = [[] for _ in range(n + 1)]

li = deque([])

result = 0

for _ in range(m):
    a, b = map(int, input().split())

    dic[a].append(b)
    dic[b].append(a)


def Ice_Cream(cnt):
    global result

    if cnt == 3:
        for data in li:
            for num in dic[data]:
                if dp[num] == 1:
                    return

        # print(li)
        result += 1
        return

    else:
        for i in range(1, n + 1):
            if dp[i] == 0:
                if li:
                    if li[-1] < i:
                        continue

                dp[i] = 1
                li.append(i)

                Ice_Cream(cnt + 1)

                dp[i] = 0
                li.pop()


Ice_Cream(0)
print(result)

 

 

Ice_Cream 함수를 보자.

아이스크림을 3개를 순서가 상관있는 순열로 고른다.

3개를 골랐다면, 섞으면 안 되는 조합에 해당하는 것이 있는지 확인한다.

 

3개의 아이스크림을 하나씩 꺼냈을 때,

해당 아이스크림과 조합하면 안 되는 아이스크림의 dp가 1이라면

섞으면 안 되는 조합이 포함된 것이다.

 

따라서, result를 플러스해 주지 않고 return한다.

 

 

 

 

시간 초과 때문에 PyPy3으로 제출하였다. 

이런 식으로 풀지 않고 DFS로 풀었다면 Python3로도 통과했을 것 같다.