나의 풀이 :

def dfs(path):
if len(path) == n:
return path[:]
for i in range(n):
if visited[i]:
continue
if not path or screws[path[-1]][1] == screws[i][0]:
visited[i] = 1
ret = dfs(path + [i])
if ret:
return ret
visited[i] = 0


T = int(input())
for tc in range(1, T + 1):
n = int(input())
line = input().split()
screws = [tuple(line[i:i+2]) for i in range(2*n) if i % 2 == 0]
visited = [0]*n
ret = dfs([])
ans = []
for i in ret:
ans.extend(screws[i])
print('#{} {}'.format(tc, ' '.join(ans)))


한마디 :

사실 위 풀이는 엄밀히 말하면 틀렸다. 모든 tc에서 남는 나사 없이 모두 연결된 상태의 정답이 존재한다고 가정하고 풀었기 때문이다.