[문제 풀이 25] 코드 트리 - 특정 조건에 따라 줄 세우기

특정 조건에 따라 줄 세우기

 

• 문제 유형 : 정렬, Backtracking
• 사용언어 : Python
• 난이도 : 실버 2
• 출처 : 코드 트리

 

https://www.codetree.ai/training-field/search/problems/line-up-according-to-specific-conditions?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

from itertools import permutations

# 소 이름
cows = ["Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"]

# N 줄
N = int(input())

# 
constraints = []
for _ in range(N):

    parts = input().split()
    A = parts[0]
    B = parts[-1]

    constraints.append((A, B))

def valid_order(perm):
    index_map = {cow: idx for idx, cow in enumerate(perm)}
    
    for a, b in constraints:
        if abs(index_map[a] - index_map[b]) != 1:
            return False

    return True

sorted_cows = sorted(cows)

for perm in permutations(sorted_cows):
    if valid_order(perm):

        for cow in perm:
            print(cow)
        break