[프로그래머스] [Python] Level3_여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

dfs 사용하는 문제

1차 시도

def solution(tickets):
    graph = {}
    #dictionary = graph
    #dic key = 출발도시명
    #dic value = 도착도시명
    for ticket in tickets:
        graph[ticket[0]] = graph.get(ticket[0], []) + [ticket[1]]
    for i in graph:
        graph[i].sort(reverse = True)
    
    #dfs
    stack = ["ICN"]
    path = []
    
    while len(stack) > 0: #child가 있을 때까지
        top = stack[-1] #비교하고싶은애
        if top not in graph or len(graph[top]) == 0: #top에서 가는 표가 없거나 다 비교 했으면
            path.append(stack.pop())
        else : #다 비교 안했어
            stack.append(graph[top][-1]) #child가져옴
            graph[top] = graph[top][:-1] #한번stack에 갔다오면 다시 안감
    return path[::-1] #뒤에서부터return

 

graph는 아래처럼 표시된다

#tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]
{'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['SFO', 'ICN']}

💡최종로직

0. 주어진 graph를 dictionary로 표현하기 (key : 출발도시명, value : 도착도시명)

0. graph안에 value를 역순으로 정렬 (pop할거라 결과가 알파벳순으로 하려면 역순으로 정렬해두어야함)

====dfs====

1. stack에 첫 출발지인 "ICN"을 넣어둠

2. return할 list 선언

3. stack이 있으면 (child가 계속 있으면)

  3-1. stack가장 위에 있는 애가 graph에 없거나 child node가 없으면, 다 비교한 것이니

    return list에 append

  3-2. 그게 아니라 아직 child node가 남아있으면

    3-2-1. stack에 graph에서 가장 위에 있는 애 child를 하나 가져옴

    3-2-2. 한번 stack에 갔다오면 다시 안가니까 graph에서 child하나 빼줌 (Slicing)

4. return list를 역순으로 반환 (child node가 계속 위에 쌓이니까 parent는 계속 밑에 깔려있음)

 

경로 >> DFS (Stack 활용)

BFS (Queue활용)