Programmers - 여행 경로

문제 링크

DFS 로 풀었다. 1,2번 케이스에서 계속 틀려서 질문하기에 있는 여러 테스트 케이스들을 돌려보면서
주의사항을 생각 할 수 있었다.

주의해야 할 점

1. 같은 경로 티켓이 여러개인 경우

EX) [["ICN","AAA"], ["AAA","BBB"],["BBB","AAA"],["AAA","BBB"],["BBB","AAA"]]

2. 우선순위가 뒤에 있는 경로를 먼저 갔다와야 할 수 밖에 없는 경우

EX) [["ICN","AAA"],["ICN","BBB"],["BBB","ICN"]]

주의사항 처리 방법

1) graph에 티켓 정보를 담아두고, 다음 node 방문 전 ticket을 제거
2) 잘못된 경로(모든 티켓을 소비 할 수 없는)로 들어간 경우 False를 return 받도록 함.
false인 경우 제거한 티켓을 순서상 가장 뒤에 추가하고 answer에 더했던 node를 삭제

def solution(tickets):
    answer = []
    graph = dict()

    for [fr, to] in tickets:
        if graph.get(fr) == None:
            graph[fr] = []
        graph[fr].append(to)

    for fr in graph.keys():
        graph[fr] = sorted(graph[fr])

    def get_ticket_counts(graph):
        count = 0
        for key in graph.keys():
            count += len(graph[key])
        return count

    def dfs(node):
        answer.append(node)
        # print("dfs", node, answer)
        if get_ticket_counts(graph) == 0:
            # print("completed")
            return True

        if graph.get(node) == None or len(graph[node]) == 0:
            return False

        for next in graph[node][:]:
            graph[node].remove(next)
            completed = dfs(next)

            if completed:
                return True
            else:
                graph[node].append(next)
                answer.pop()
                # print("not completed", node, next, answer)

    dfs("ICN")
    # print("answer", answer, g)
    return answer