[Python/파이썬] 백준 15566번 개구리 1

15566번: 개구리 1

 

코드

n, m = map(int, input().split())
# 각 개구리의 음식, 취미, 가족, 철학에 대한 흥미도
frogs = [[]]+[list(map(int, input().split())) for _ in range(n)]
# 개구리가 선호하는 연꽃의 번호
frog_prefers = [set()]+[set(map(int, input().split())) for _ in range(n)]
# 통나무 통로의 대화 주제
topics = [[-1]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, t = map(int, input().split())
    topics[a][b] = t
    topics[b][a] = t

lotus_frog = [-1]*(n+1)  # 각 연꽃에 사는 개구리 번호


def bt(idx):
    if idx > n:
        if check():
            print("YES")
            print(*lotus_frog[1:])
            exit()
        return
    for nx in frog_prefers[idx]:    # 연꽃 번호
        if lotus_frog[nx] == -1:    # 아직 아무도 차지하지 않았는지
            lotus_frog[nx] = idx
            bt(idx+1)
            lotus_frog[nx] = -1


def check():
    for i in range(1, n+1):  # 연꽃 번호 1
        for j in range(1, n+1):  # 연꽃 번호 2
            if topics[i][j] > 0:
                fa = lotus_frog[i]
                fb = lotus_frog[j]
                t = topics[i][j]
                if frogs[fa][t-1] != frogs[fb][t-1]:
                    return False
    return True


bt(1)
print("NO")

 

1. 백트래킹: 개구리 위치 잡기
2. 브루트포스: 그 위치에 있으면 모든 통나무에서 정해진 주제로 가능한지 확인

2개의 과정으로 이루어졌다.

백트래킹으로 개구리를 1번부터 차례대로 선호하는 연꽃들에 놓을 수 있다면 그 자리에 놓고, 재귀함수를 호출한다. 이렇게하여 N마리의 개구리를 모두 놓는다면 이제 이 배치로 모든 통나무에서 정해진 주제로 대화가 가능한지 알아봐야 한다.

 

대화가 가능한지 알아보는것은 브루트포스로 풀었다. 모든 연꽃 간에 다리가 있는지 조사하여 다리가 있다면, 즉 topics[i][j]의 값이 0 초과로 정해진 주제가 있다면 해당 주제로 i번 연꽃의 개구리와 j번 연꽃의 개구리가 대화 가능한지 알아본다.

모든 통나무에서 대화가 가능하다면 그때의 개구리 배치를 출력하고 프로그램을 종료한다.

 

 

문제가 어렵지는 않은데 주어진 입력값들이 많아서 너무 헷갈린다....