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

1. 문제

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

프로그래머스

 

 

2. 풀이

 

드디어 Lv 3 문제도 좀 적응한거같다 ㅠㅠ

 

이 문제는 dfs로 이용해서 풀었다,, 이유는 진입경로를 끝까지 파서 마지막까지 닿으면 되기 때문이다.

대신 그럴려면 sort로 알파벳 순서대로 정렬해줘야한당

 

1) 주어진 경로를 유방향 그래프 (directed graph) 의 인접리스트로 구현한다.

유방향 그래프 생성 : 발그림 ㅈㅅ합니다 ,,

** 내가 추가해서 썼던 테케,, [["ICN", "B"], ["ICN", "C"], ["C", "ICN"]] -> ["ICN", "C", "ICN", "B"]

2) 각 리스트를 알파벳 순서대로 정렬해준다.

3) dfs를 돌리는데, 대신 return으로 visited 리스트를 받아서 끝까지 완성된 경우에 최종 return을 해준다. 정답이 아닌 경우엔 길이가 다르거나 / 중간에 return되면서 NoneType이 return된다.

 

## code ##

import collections
import sys
sys.setrecursionlimit(10**9)
def solution(tickets):
    graph = collections.defaultdict(list)
    for tic in tickets:
        graph[tic[0]].append(tic[1])
    
    # 알파벳 순 정리
    for key in graph.keys():
        graph[key].sort()
    
    def path(graph, visited, cur):
    	## 길이가 len(tickets)랑 같아서 마지막 한 경로만 있으면 되어서 마지막 경로 추가하고 리턴
        if len(visited) == len(tickets) and not graph[cur]:
            visited.append(cur)
            return visited
        else:
            visited.append(cur)
            i = 0
            while i < len(graph[cur]):
                next = graph[cur].pop(0)
                new_visit = visited.copy()
                answer = path(graph, new_visit, next)
                # answer가 정답 길이만큼 같지 않으면 지나감, 맞으면 정답!
                if answer is not None and len(answer) == len(tickets) + 1:
                    return answer
                graph[cur].append(next)
                i += 1

    visited = []
    visited = path(graph, visited, "ICN")
    print(visited)
    
    return visited

 

음 일단 알파벳순으로 정리했기 때문에, 처음으로 모든 방문 경로가 완성되는 경우가 정답이 맞다!!

정리안했으면 알파벳 순이 보장이 안돼서 테케2번부터 틀렸을듯 합니다.