백준 22239 가희와 읽기 쓰기 놀이2(python)

문제

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

22239번: 가희와 읽기 쓰기 놀이 2

---

구현하기 까다로웠던 문제였습니다. DFS 방식으로 접근하여 풀었습니다.  주어진 제약 조건에 맞게 카드와 사람들 간에 관계를 연결하여 푸는 문제였습니다. 과정은 다음과 같습니다.

• 주어진 제약들과 카드 값들을 입력받고, 제약에 맞게 카드값들에 플레이어 번호를 넣어 줍니다.
• 탐색하는 함수에서는 만들어내야하는 결괏값이 있는지 확인하고, 있다면 값을 가지고 있는 플레이어를 찾아 제약에서 가장 앞에 있는 값을 비교하여 맞다면 제약에서 꺼내 줍니다.
• 이후에 다음 결과 리스트를 탐색하고 계속 순회하며 값들을 찾아줍니다. 값이 없다면 종료시켜 줍니다.
• 최종적으로 C번 카드까지 전부 봤을때의 결과 리스트를 출력해 줍니다.

---

소스코드 

import sys
from collections import defaultdict
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N, C = map(int, input().split())
res_list = list(map(int, input().split()))
const = []
dic = defaultdict(set)

# 제약 부분
for i in range(N):
    p_const = list(map(int, input().split()))
    const.append(deque(p_const[1:]))

# 카드 숫자 별로 값 저장
card = {}
for i in range(1, C+1):
    in_ = input().split()[1]
    card[i] = int(in_)

# 카드 값마다 내야하는 사람 번호
for i in range(N):
    for j in const[i]:
        dic[card[j]].add(i)


ans = []


def go(idx):
    if idx == C:
        print(*ans)
        sys.exit()

    # 값이 없다면 그냥 종료
    if res_list[idx] not in dic:
        print(-1)
        sys.exit()

    for player in dic[res_list[idx]]:
        if const[player] and card[const[player][0]] == res_list[idx]:
            tmp = const[player].popleft()  # 현 플레이어의 가장 앞 번호 카드
            ans.append(player+1)

            go(idx+1)

            const[player].appendleft(tmp)

            ans.pop()


# for num in res_list:
#     if num not in dic:
#         print(-1)
#         exit()

go(0)
print(-1)