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

문제보기

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

프로그래머스

 

풀이 & 코드

해당 문제는 쉽게 생각하고 접근했다가 곤혹을 좀 치뤘다ㅎ 보통 bfs/dfs 문제는 depth를 따라 내려가다 last leaf에서 멈춘다. 하지만 이 문제는 last leaf에서 남은 edge가 있다면 다시 되돌아 가 순서를 바꾸어야 한다.

 

만약 [["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]] 이런 길이 있다고 해보자. 그렇다면 다음과 같이 길이 그려질 것이다.

문제에서 경로가 2가지 이상일 때는 알파벳 순서가 빠른 값을 찾으라고 하였기 때문에 ICN -> A 다음으로 B를 먼저 탐색하게 된다. 하지마 B를 가게 된다면 C로 갈 수가 없다. 따라서 C를 먼저 간 후에 다시 A로 돌아와 B, D로 가야한다. 필자는 재귀함수를 이용해 이 문제를 해결했다. bfs함수에서는 시작 지점에서 갈 수 있는 길이 다양하다면 알파벳 순으로 재귀함수를 호출한다. 만약 갈 수 있는 길이 더 이상 존재하지 않는 다면 빈 list를 반환하고 모든 tickets을 사용하면 경로를 담은 list를 반환한다. 따라서 호출한 bfs의 결과값이 빈 list라면 해당 경로가 올바르지 않다는 것을 의미하기에 다른 경로로 진행을 한다.

def bfs(tickets, answer):
    start = answer[-1]
    if len(tickets) == 0:
        return answer
        
    possible_ends = [ticket[1] for ticket in tickets if ticket[0] == start]
    for end in possible_ends:
        _tickets = tickets[:]
        _tickets.remove([start, end])
        _answer = answer[:] + [end]
        result = bfs(_tickets, _answer)
        
        if len(result):
            return result
        
    return []


def solution(tickets):
    tickets.sort(key = lambda x: x[1])
    answer = ["ICN"]
    
    return bfs(tickets, answer)

 

추가 코드

다른 사람들의 코드를 살펴보던 중 재밌는 코드가 있어서 추가로 포스팅하고자 한다.

 

사실 필자는 재귀함수를 별로 선호하지 않는다. 물론 재귀함수를 사용하면 인사이트도 쉽게 떠오르고 코드도 간결해지는 경우가 많다. 하지만 대다수의 경우 재귀함수를 사용하면 깊이 제한에 걸린다. 코딩테스트가 효율성과 정확성을 따지기 때문에 인풋의 크기가 굉장히 큰 경우가 많기 때문이다. 그래서 위의 코드를 작성하면서도 상당히 불안했다. 그럼에도 딱히 방도가 떠오르지 않아 재귀로 작성했는데 프로그래머스의 최대 장점! '다른 사람의 풀이' 에 재귀함수를 쓰지 않은 코드를 발견했다. 

 

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    for r in routes:
        routes[r].sort(reverse=True)
    stack = ["ICN"]
    path = []
    while len(stack) > 0:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        else:
            stack.append(routes[top][-1])
            routes[top] = routes[top][:-1]
    return path[::-1]

 

자 그럼 코드르 뜯어보며 이해해보자!

 

routes = {}
for t in tickets:
	// dict안에 ticket의 시작이 있다면 그 값에 ticket의 도착 지점을 추가하고, 없다면 []에 도착 지점을 추가.
    routes[t[0]] = routes.get(t[0], []) + [t[1]]
for r in routes:
	// key마다 value값들을 내림차순으로 정렬
    routes[r].sort(reverse=True)

먼저 routes라는 dictionary에 공항마다 도착지점을 정리해준 뒤에 도착지점을 내림차순으로 정렬한다. 위에서 말한 ["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]] 의 케이스의 경우 다음과 같이 결과값이 나올 것이다.

{'ICN': ['A'], 'A': ['C', 'B'], 'C': ['A'], 'B': ['D']}

 

여기까지가 데이터 전처리 같은 느낌이다. 이제 알고리즘 부분인데 탐색하는 길을 stack 넣고 만약 길이 없다면 해당 지점을 path로 옮긴다. 그렇게 되면 마지막으로 도착해야 하는 오히려 D, B가 먼저 path에 들어가게 되고 모든 길을 다 탐색한 뒤에는 stack에 있는 값들이 역순로 path로 들어가게 돼 결국 path는 우리가 원하는 정답의 reverse가 된다! (ㄷㄷ 핵천재)

while len(stack) > 0:
    top = stack[-1]
    if top not in routes or len(routes[top]) == 0:
        # 갈 수 있는 길이 없다면 stack에서 path로
        path.append(stack.pop())
    else:
        # 갈 수 있는 길이 있다면 dict에서 제거 후 stack으로
        stack.append(routes[top][-1])
        routes[top] = routes[top][:-1]
    print(top, path, stack, routes)
return path[::-1]

혹시 이해가 잘 안되는 분들을 위해 print(top, path, stack, routes)을 출력해보았다.

출력값