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

출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/43164

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

 

그냥 음 내 취향인 문제다.

틀은 잘 짰는데 예외 처리에서 오래 걸렸다.

 

 

먼저, 생각해야 할 부분

 

1. 같은 티켓이 2장일 수 있다.

 

#Input
[["ICN", "SFO"], ["SFO", "ICN"], ["ICN", "SFO"]]
#Output
["ICN", "SFO", "ICN", "SFO"]

 

문제에서 '티켓 중에 중복된 티켓은 없습니다'와 같은 중복에 관한 조건이 없다면,

티켓이 중복될 수 있다는 생각을 해야한다. 중복에 관련한 조건이 있는지 먼저 찾아볼 것.

 

이 점을 고려 못해서 처음에 티켓 사용 처리를 True, False로 했다가 나중에 티켓 개수를 감소시키는 방식으로 변경하였다.

어짜피 True, False로 하나 0, 1로 하나 인식은 비슷하게 되고, 범용성은 0, 1이 더 높으므로

처음부터 0, 1로 작성하고 ±1하며 방문처리를 하는 방법이 범용성이 훨씬 높은 듯 하다.

 

2. 목표 level 도달 전에 막다른 공항에 도달할 수 있다.

 

쉽게 말해서 종료 조건 설정을 잘못한 경우인데, 나 같은 경우는 level에 도달하는 경우만 고려하여 return 해주었다.

문제는 작성할 때, 각 티켓의 출발지만을 key 값으로 주었기 때문에,

level에 도달하지 않을 시 막다른(나가는 티켓이 없는) 도착지를 key값으로 조회하는 경우가 발생하였다.

당연히 막다른 도착지의 경우 출발지인 적이 없기 때문에 key값에 없어 런타임 에러가 발생하였다.

 

처음 시도한 방법은 arrive 역시 key값으로 넣어 정상적으로 돌아가게 만들었다.

그러나 곰곰히 생각해보니 이 역시 막다른 길에서 backtracking을 해야하는 경우이므로

현재 공항이 tickets의 key(출발지)로 존재하지 않는 경우에 대해 종료 조건을 추가해주었다.

 

---

 

풀이

 

stack = []

def DFS(current, tickets, level, n):
    global stack
    
    if level >= n:
        #n개되면 stack return
        return stack
    
    if current not in tickets:
        #level이 n보다 작은 데 막다른 공항이면, 실패
        return False
    
    for arrive in tickets[current].keys():#도착지를 가져와서
        if tickets[current][arrive] != 0:#도착지로 향하는 티켓이 남아 있다면(0개가 아니면)
            stack.append(arrive)#stack에 넣고
            tickets[current][arrive] -= 1 #항공권 소비

            if DFS(arrive, tickets, level + 1, n):
                #DFS 결과가 stack(True)면 그만하고 return, 도달하지 못해서 False면 밑으로
                return stack

            tickets[current][arrive] += 1 #도달하지 못했으므로 항공권 다시 복구
            stack.pop()#stack에서 제거
            
    return False

def makeDict(tickets):
    tickets_dict = dict()
    
    for depart, arrive in tickets:
        tickets_dict.setdefault(depart, dict())#같은 항공권 존재 가능
                                
        tickets_dict[depart].setdefault(arrive, 0) #값으로 개수를 넣는다.
        tickets_dict[depart][arrive] += 1
        
    for key, value in tickets_dict.items():#내부 사전의 key값에 따라 정렬
        tickets_dict[key] = dict(sorted(value.items(), key=lambda x:x[0]))
        
    return tickets_dict

def solution(tickets):
    #DFS
    #사전순으로 정렬 후 호출
    #모든 티켓을 사용하면 print하고 종료
    #dict(ICN : dict([ATL : 1], [SFO : 2]))
    n = len(tickets) + 1

    tickets = makeDict(tickets)
    
    stack.append('ICN')
    answer = DFS('ICN', tickets, 1, n)
    
    return answer

 

항공권을 전부 사용하는 알파벳 순서를 다 쓰는 경로를 찾기만 하면 되기 때문에

BFS보다는 DFS라는 생각이 들어서 DFS로 접근하였다.

알파벳 순서로 미리 정렬을 해놓고 DFS로 접근하면 가장 먼저 찾은 경로가 정답이기 때문이다.

 

구현은 재귀의 방식을 그대로 가져갔다.

 

---

시간 복잡도

 

-

 

알게 된 점

 

dictionary.setdefault() 함수

 

dictionary = dict()

dictionary.setdefault(key, defaultValue)

 

사전의 기본값을 처리할 때,

그동안 in 연산자를 사용해서 key가 사전 내에 있는지 먼저 체크하거나 try ~ except 문을 사용해서 처리해왔다.

그런데 사전 내에 key의 존재 여부를 체크해주고 없을 시 기본값을 생성해주는 setdefualt() 함수가 있더라.

 

위와 같은 형태로 작성하면 dictionary 변수 내에서 key를 조회하고 없을 경우 defaultValue로 생성해준다.

그 밑에 후처리를 하면 된다.

 

defaultdict

 

def makeDict(tickets):
    tickets_dict = dict()
    
    for depart, arrive in tickets:
        tickets_dict.setdefault(depart, dict())#같은 항공권 존재 가능
                                
        tickets_dict[depart].setdefault(arrive, 0) #값으로 개수를 넣는다.
        tickets_dict[depart][arrive] += 1
        
    for key, value in tickets_dict.items():#내부 사전의 key값에 따라 정렬
        tickets_dict[key] = dict(sorted(value.items(), key=lambda x:x[0]))
        
    return tickets_dict

 

 위 풀이 중 일부를 가져온 것이다.

setdefault() 함수를 사용하였는데, 매 for문마다 setdefault 함수가 사용되는 것이 보기 좀 그렇다.

이를 해결할 수 있는 자료형이 바로 collections의 defaultdict이다.

 

from collections import defaultdict

myDict = defaultdict(function return defaultValue)

 

defaultdict 자료형은 위와 같이 선언할 수 있다.

collections을 불러와서 defaultdict을 import하여 사용한다.

defaultdict의 매개변수로는 기본값이 아니라 defaultValue값을 return해주는 함수가 들어간다.

 

결론적으로 setdefault()를 사용한 코드를 defaultdict으로 풀 경우 아래와 같은 풀이가 된다.

 

from collections import defaultdict

def makeDict(tickets):
    tickets_dict = defaultdict(lambda: defaultdict(int))
    
    for depart, arrive in tickets:
        tickets_dict[depart][arrive] += 1
        
    for key, value in tickets_dict.items():#내부 사전의 key값에 따라 정렬
        tickets_dict[key] = dict(sorted(value.items(), key=lambda x:x[0]))
        
    return tickets_dict

 

외부의 defaultdict은 key에 대해 내부의 defaultdict을 기본값으로 가지는 사전이다.

내부의 defaultdict은 key에 대해 0을 기본값으로 가지는 함수이다.

(int 함수는 0을 return)

 

고찰

 

-

 

Github

프로그래머스 - 여행 경로

 

Reference

Recursion(재귀)

[파이썬] 사전의 기본값 처리 (dict.setdefault / collections.defaultdict)