[프로그래머스/Python] 여행경로 - Level3

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

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

이 문제는 모든 값을 확인하면서 경로를 구하는 문제이기 때문에 DFS 문제였다. 각 시작점의 인접 리스트를 구한 후 도착점을 알파벳 순서로 정렬하는 것까지는 생각할 수 있었다. 처음에는 재귀함수로 이 문제를 풀려고 했었다. 인접리스트에 값이 있으면 재귀함수를 호출하고 재귀함수가 끝나면 경로에 추가하는 식으로 했는데 뭔가 잘 안되었다... 결국 dfs 수행하는 부분은 다른 사람 코드를 참고하게 되었다. 경로를 역순으로 채우고 answer를 역순으로 출력하는 것은 전혀 생각하지 못했던 부분이었다.

from collections import defaultdict

def solution(tickets):
    graph = defaultdict(list)
    
    # 각 시작점의 인접 리스트 구하기
    for key, value in tickets:
        graph[key].append(value)
        
    # 딕셔너리의 value(도착점) 알파벳순 정렬
    for g in graph:
        graph[g].sort()

    answer = dfs(graph) # dfs 수행
    
    return answer

# dfs 수행 메서드
def dfs(graph):
    answer = [] # 경로
    stacks = ['ICN'] # 스택
    
    while stacks:
        stack = stacks[-1] # 가장 위에 있는 데이터
        
        if stack not in graph or len(graph[stack]) == 0: # 시작점에 없거나 더 이상 갈 곳이 없는 경우
            answer.append(stacks.pop())
        else:
            stacks.append(graph[stack].pop(0)) 
        
    return answer[::-1] # 역순 출력

1. 각 시작점의 인접리스트를 구한다. 인접리스트는 graph = { '시작점' : [도착점, 도착점, ..] , ... } 형식으로 저장된다.

2. graph의 도착점을 알파벳 순으로 정렬한다. 

3. dfs를 통해 모든 점을 확인한다.

    3-1. 스택에 시작점인 'ICN' 을 넣은 후 스택에 값이 없을 때까지 반복한다.

    3-2. 가장 위에 있는 데이터(stack) 이 시작점에 없거나 더 이상 갈 곳이 없는 경우 경로에 stack을 추가한다.

    3-3. 위 조건이 아니라면 graph에서 pop하여 다음에 갈 곳을 stacks에 추가한다.

4. 경로를 역순으로 출력한다.

 

알게된 점

▶ defaultdict

defaultdict 클래스의 생성자로 기본값을 생성해주는 함수를 넘기면, 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해준다. 딕셔너리에 값을 넣을 때 키가 있는지 없는지 확인할 필요가 없어서 편하다.

from collections import defaultdict

def countLetters(word):
    counter = defaultdict(int)
    for letter in word:
        counter[letter] += 1
    return counter