[SWEA][Python3] 1259. [S/W 문제해결 응용] 7일차 - 금속막대

나의 풀이 :

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에서 남는 나사 없이 모두 연결된 상태의 정답이 존재한다고 가정하고 풀었기 때문이다.