Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 여행경로

[여행경로]

• 두 가지의 접근으로 문제를 풀어 보았다.

1. Backtracking

tickets의 길이를 $n$이라 할 때, 탐색중인 경로의 길이가 $n+1$이란 것은 모든 티켓을 사용했다는 의미이다.

• 이를 이용하여 Base condition을 설정하고 백트래킹을 이용할 수 있다.

2. Eulerian path

• 주어진 항공권을 모두 이용하고, 항공권은 한 번만 이용한다는 점을 생각하면 Eulerian path(한붓그리기)로 볼 수 있다.
• 이는 Hierholzer’s algorithm으로 $O(E)$에 구할 수 있다.

Solution 1-1. Backtracking $O(n \cdot \prod_{i=1}^{m}{\text{outdeg}(v_i)} + 2n)$

from collections import defaultdict

def solution(tickets):
    adj = defaultdict(list)
    for u, v in tickets:
        adj[u].append([v, False])

    ret = []

    def backtracking(cur, path=["ICN"]):
        if len(path) == len(tickets) + 1:
            ret.append(path[:])
            return

        for nxt in adj[cur]:
            if not nxt[1]:
                nxt[1] = True
                path.append(nxt[0])
                backtracking(nxt[0], path)
                path.pop()
                nxt[1] = False

    backtracking('ICN')
    return min(ret)

• 먼저 tickets를 순회하며 인접 리스트를 구성한다. 이 때, 항공권의 사용 처리(방문 처리)를 위해 이를 나타낼 변수를 False로 초기화하여 함께 묶어 놓는다.
• 백트래킹을 마치고 나면, ret에는 가능한 모든 경로들이 모여있게 된다. 알파벳 순서가 앞서는(사전 순으로 가장 앞서는) 경로를 return하기 위해 min(ret)으로 return한다.

Solution 1-2. Backtracking $O(n \lg n + \prod_{i=1}^{m}{\text{outdeg}(v_i)})$

from collections import defaultdict

def solution(tickets):
    adj = defaultdict(list)
    for u, v in sorted(tickets):
        adj[u].append([v, False])

    def backtracking(cur, path=["ICN"]):
        if len(path) == len(tickets)+1: return path

        for nxt in adj[cur]:
            if not nxt[1]:
                nxt[1] = True
                path.append(nxt[0])
                if ret:= backtracking(nxt[0], path): return ret
                path.pop()
                nxt[1] = False

    return backtracking('ICN')

• 인접 리스트를 구성할 때, 진출 노드들이 정렬된 상태로 구성해놓고 백트래킹을 수행하면, 첫 번째로 구성된 길이가 $n+1$인 path는 알파벳 순서가 가장 앞서는 경로이다.
• 이러한 경로를 발견하자마자 조기종료하므로 Solution 1-1.에서 98.86ms가 걸렸던 TC #1이 0.03ms로… 줄어든다.

Solution 2-1. Eulerian Path (Hierholzer’s Algorithm) $O(n \lg n + 3n)$

from collections import defaultdict

def solution(tickets):
    adj = defaultdict(list)
    for u, v in sorted(tickets, reverse=True):
        adj[u].append(v)
    
    stack = ["ICN"]
    ret = []

    while stack:
        if adj[stack[-1]]:
            nxt = adj[stack[-1]].pop()
            stack.append(nxt)
        else:
            ret.append(stack.pop())
    
    return ret[::-1]

• 문제의 제한사항을 통해 모든 도시를 방문할 수 있음이 보장되어있으므로, Eulerian path를 구하기 위한 Hierholzer’s Algorithm을 이용할 수 있다.

Solution 2-2. Eulerian Path (Hierholzer’s Algorithm) $O(n \lg n + 3n)$

from collections import defaultdict

def solution(tickets):
    adj = defaultdict(list)
    for u, v in sorted(tickets, reverse=True):
        adj[u].append(v)

    ret = []
    def traversal(cur):
        while adj[cur]:
            traversal(adj[cur].pop())
        ret.append(cur)

    traversal("ICN")
    return ret[::-1]

• Hierholzer’s Algorithm의 또다른 구현이다.

---

References

• Wikipedia, Eulerian path