[파이썬]프로그래머스 여행경로

링크

프로그래머스 여행경로

처음 시도 했을 땐 1, 2번 테스트케이스를 통과를 못했다.
그 후 찾아보니 오름차순으로만 탐색할 경우 끝까지 탐색해야한다는 조건을 만족하지 못하는 경우가 생기는 것을 알았다.

예를 들어 티켓이 [["ICN","AAA"], ["ICN", "BBB"], ["BBB", "ICN"]] 인 경우
ICN 에서 AAA를 먼저 탐색하게 되면 모든 정점을 방문하지 못한다.

해당 조건을 만족시키려면 AAA에서 출발하는 티켓이 없는경우 즉, 경로의 종단에 도착했을 경우는 경로의 가장 마지막에 넣어주면 된다.

이런식으로 코드를 작성하면 ans에는 경로의 종단부터 역으로 생기는 경로가 저장된다.
마지막에 뒤집어서 출력해주면 된다.

정답 코드

def solution(tickets):
    adj = {} #인접리스트
    for dep, arr in tickets:
        if adj.get(dep) == None:
            adj[dep] = [arr]
        else:
            adj[dep] += [arr]

    for dep in adj.keys():
        adj[dep].sort(reverse=True) #가장 위부터 꺼내서 쓸거라 오름차순
        #가장 위에 사전순 제일 빠른게 올라옴

    s = ["ICN"] # 인천에서 시작
    ans = []
    while s:
        depart = s.pop() #스택에서 꺼냄 -> 출발지
        # 만약 출발지가 실제로 출발가능하고 (인접리스트에 키로 존재)
        # 아직 사용안한 티켓이 있으면 (밸류의 길이가 양수)
        if depart in adj and len(adj[depart]) > 0:
            s.append(depart) #다시 스택에 넣어주고
            s.append(adj[depart].pop()) #가장 위에있는 티켓을 스택에 넣어줌
        else: # 해당 출발지에서 출발하는 티켓이 없는 경우
            # 바로 정답에 넣어줌
            # 왜냐하면 더이상 갈곳이 없기때문에 굳이 스택에 넣어서 탐색할 필요가 없음
            ans.append(depart)

    return ans[::-1]

알게된 것👨‍💻

• 항상 정수형으로 dfs만 다루다가 문자형으로 다루니 어색했다. 이부분도 연습이 많이 필요할 것 같다.
• 조건을 잘 읽고 더 자세하게 조건을 분기시키는 연습이 더 필요하다. 항상 반례를 못찾아서 한번에 통과가 안된다.