[코딩테스트]여행경로(DFS)

건너별·2022년 5월 6일
0

algorithm

목록 보기
26/27

문제 풀기

핵심 ideation

  • dfs를 stack으로 구현해야 쉽게 풀 수 있는 문제.
  • 방문한 경로를 기록해놓고 다시 방문 안하는게 아니라, pop()으로 없애주고 자연스럽게 모든 코스를 순회하도록 하는 것이 핵심
  • defaultdict 활용해야 함.
from collections import defaultdict
def dfs_recur(graph, start, visited=[]):
    # visited.append(start)
    
    # for node in graph[start]:
    #     if node not in visited:
    #         dfs_recur(graph,node,visited)
    # return visited
    stack=[]
    stack.append(start)
    while stack:
        tmp = stack[-1]
        if not graph[tmp]: # 없으면 visited에 추가해주기
            node = stack.pop()
            visited.append(node)
        else: # 있으면
            stack.append(graph[tmp].pop())
    visited.reverse()
    return visited


def solution(tickets):
    dic = defaultdict(list)
    
    for a,b in tickets:
        dic[a].append(b)
    for key, blist in dic.items():
        blist.sort(reverse=True)
        
        
    print(dic)
    return dfs_recur(dic,'ICN')
profile
romantic ai developer

0개의 댓글