날짜: 2022년 1월 31일 오후 5:51

코드

Algorithm/43164.py at main · Junroot/Algorithm

풀이

현재 위치에서 탈 수 있는 티켓을 계속 고르면서, 모든 티켓을 사용할 수 있는 경우를 찾으면 반환하는 함수를 만들었다. dfs이기 때문에 재귀함수를 이용했고, 현재 반환한 값이 성공적으로 찾았는지 판별하기위해 (성공여부, 경로) 튜플 형태로 반환했다. 그리고 알파벳 순서가 앞서는 경로를 우선으로 해야됐기때문에 탐색 시작전에 tickets를 한 번 정렬시켰다.

다른 사람 풀이를 봤는데, python의 경우 리턴값을 따로 쓰지 않으면 None이 리턴되는 것을 이용할 수 있었다. 이 방식을 이용해서 굳이 튜플이 아니라 경로만 리턴하는 방법도 있다는 것을 알게되었다.

def dfs(graph, N, key, footprint):
    print(footprint)

    if len(footprint) == N + 1:
        return footprint

    for idx, country in enumerate(graph[key]):
        graph[key].pop(idx)

        tmp = footprint[:]
        tmp.append(country)

        ret = dfs(graph, N, country, tmp)

        graph[key].insert(idx, country)

        if ret:
            return ret