[백준] 20528 - 끝말잇기 (Python)

문제 출처 :

www.acmicpc.net/problem/20528

20528번: 끝말잇기

문제 해설 : 

• GoodBye 2020! 의 A번 문제이다!
• 순서가 난이도 대로 나열되어있기 때문에 쉬운 문제라고 생각하고 접근했는데 의외로 애먹었던 문제이다.
• 입력되는 단어의 갯수가 최대 100개 밖에 안된다. 때문에 완전탐색으로 찾아도 충분하다.
• 두 가지 부분을 나눠서 생각했는데
  1. 첫번째 단어는 뭘로 시작?
  2. 첫번째 단어가 정해지면 끝말잇기를 해야하는 알파벳들이 정해진다. 이미 끝말잇기에 쓰인 단어들을 제외하면서 재귀로 풀면된다.

import sys

input = sys.stdin.readline

n= int(input())

words = list(map(str,input().split()))
idxs = dict()

for i in range(n):
    idxs[i]=0

def word_play(word,cnt):
    global idxs
    #print(word)
    str_ = word[-1]
    if(cnt==n):
        return 1

    for i in range(n):
        if(idxs[i]==0 and words[i][0]==str_):
            idxs[i]=1
            #print()
            if(word_play(words[i],cnt+1)):
                return 1
            idxs[i]=0
    return 0

print(word_play(words[0],0))