[n2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 in python

---

이 문제를 보자마자

dfs로 풀어야겠다고 생각함.

 

일단 조합하면 안되는 숫자들은

딕셔너리에 저장했다.

 

1->2인 경우

서로 선택하면 안되는거니까

딕셔너리에 각각 값을 넣어주었다.

 

 

* 딕셔너리 value값 여러개일 때 처리해줘야 하는 방법 *

딕셔너리의 value값이

여러개일 경우

dic[i] = []로 초기화하고

값은 append를 이용해서 넣어주면 된다.

 

 

아이스크림이 총 5개 있다.

1 2 3 4 5

 

그 중에 3개의 아이스크림을 선택하는 경우의 수를

구하는 문제이다.

 

근데 조합해선 안될 아이스크림들이 있다.

1번,2번 아이스크림

3,4번 아이스크림

1,3번 아이스크림

 

-> 즉 1번 아이스크림은 2번,3번과 같이 선택될 수 없다.

2번,3번 아이스크림도 1번 아이스크림과 선택될 수 없다.

 

 

이 코드의 핵심은 아래와 같다.

방문한 곳이면 continue

해당 아이스크림이 조합되면 안되는 아이스크림과 같이 선택된 경우 continue

초기에 선택되어진 아이스크림 (first)하고도 비교해야하는데

이 부분을 해주지 않아서 계속 틀렸다 ㅠㅠ 

 

초기에 선택되어진 아이스크림과는 비교되어지지 않는 수도 있기때문에!

이 부분도 꼭 포함시켜줘야한다.

    for i in range(number + 1, n + 1):
        if visited[i]:
            continue
        if i in dic[number] or i in dic[first]:
            continue
        visited[i] = 1
        dfs(first,i, depth + 1)
        visited[i] = 0

---

n, m = map(int, input().split())
dic = {}
for i in range(1, n + 1):
    dic[i] = []
# dic = {i : [] for i in range(1,n+1)}

for i in range(m):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)

cnt = 0

def dfs(first,number, depth):
    global cnt
    if depth == 2:
        cnt += 1
        return

    for i in range(number + 1, n + 1):
        if visited[i]:
            continue
        if i in dic[number] or i in dic[first]:
            continue
        visited[i] = 1
        dfs(first,i, depth + 1)
        visited[i] = 0


visited = [0 for _ in range(n+1)]
for i in range(1, n + 1):
    visited[i] = 1
    dfs(i,i, 0)
    visited[i] = 0
print(cnt)