[백준2422/실버4] 한윤정이 이탈리아에서 아이스크림을 사먹는데 - Python

https://www.acmicpc.net/problem/2422

 

처음엔 그냥 모든 세가지 조합을 구한 후 웩인 조합이 들어갔는지 확인해줬다.

 

 

# 실패 코드

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]
result = 0

def dfs(i, start, select):
    global result

    if i == 3:
        if can_eat(select):
            result += 1
        return

    for j in range(start, N + 1):
        if j not in select:
            dfs(i + 1, j + 1, select | {j})

def can_eat(lst):
    for a, b in arr:
        if a in lst and b in lst:
            return False
    return True

dfs(0, 1, set())
print(result)

세가지 조합 dfs 마다 모든 웩인 조합을 하나씩 꺼내보면서 가능한 경우의 수인지 확인하는 함수가 너무 오래걸렸던 거 같다.

그래서 어떻게 확인하지 고민하다가

1. 웩인 조합을 리스트에 넣어서 (a, b)/ (b,a) / (a, c) / (c, a) / (b, c) / (c, b) 가 있는지 확인

2. 웩인 조합을 2차원 배열 (표) 로 관리해서 [a][b] / [b][c] / [c][a] 가 모두 True (먹을 수 있는 조합)인지 확인

이렇게 두가지 방법을 생각했다.

두번째 방법이 좀 더 관리하기 쉽고 직관적일 거 같아서 두번쨰 방법으로 선택해서 풀었다.

 

# 성공 코드

N, M = map(int, input().split())
can_ice = [[True] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    can_ice[a][b] = False
    can_ice[b][a] = False

result = 0

def dfs(i, start, select):
    global result

    if i == 3:
        a, b, c = select
        if can_ice[a][b] and can_ice[b][c] and can_ice[a][c]:
            result += 1
        return

    for j in range(start, N + 1):
        if j not in select:
            dfs(i + 1, j + 1, select + [j])

dfs(0, 1, [])
print(result)

 

먹을 수 있는방법 어떻게 저장하고 관리할지 고민하는 과정이 재미있는 문제였다