feat: [Lv. 3] 여행경로 (JS/TS)

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

1. 문제분석
[start, end] 단방향 엣지 3~10,000개 tickets[] -> path[] 리턴
-> start&end는 알파벳 대문자 3글자, 갈림길은 사전순(작은순)으로 탐색
-> ICN 출발 고정, 주어진 엣지 모두 탐색해야 함 (항상 모두 탐색할 수 있는 입력만 들어옴)

2. 풀어보기
[['ICN','JFK'],['HND','IAD'],['JFK','HND']]
-> ICN->JFK->HND->IAD -> 배열에 넣어 리턴
[['ICN','SFO'],['ICN','ATL'],['SFO','ATL'],['ATL','ICN'],['ATL','SFO']]
-> ICN->ATL->ICN->SFO->ATL->SFO -> 배열에 넣어 리턴

처음 만나는 폐로 -> 갈림길 까지 되돌아 나와서 다시 시작 -> 폐로 루트는 마지막에 가야 함
-> 순환이 아닌 폐로는 하나만 존재함 (오일러경로 존재가 보장되는 문제이므로)

3. 슈도코드
tickets[] 받아서 -> arrivals_by_departure{} 해시를 만들어서 -> 출발지별 도착지 []를 넣는다
-> 도착지는 우선순위큐를 사용해서 -> 뽑을 때 최소값 부터 나오도록 한다
백트래킹으로 일단 한 경로 탐색 -> 운 좋으면 한 방에 가는거고
-> 폐로 발생시 갈림길 까지 되돌아나옴 -> 걔는 마지막 길 -> 나머지는 한 방에 감

4. 구현코드

type Ticket = string;
const START = 'ICN';

const solution = (tickets: [Ticket, Ticket][]): Ticket[] => {
  const arrivals_by_departure = getArrivalsByDeparture(tickets);

  const result: Ticket[] = [];
  byBacktrackLoop(arrivals_by_departure, result, START);

  return result.reverse(); // unshift 대신 push 사용하고, reverse -> O(N)
};

const byBacktrackLoop = (map: Map<Ticket, Heap<Ticket>>, result: Ticket[], start: Ticket) => {
  const stack: Ticket[] = [start];

  while (stack.length > 0) {
    for (
      let to_heap = map.get(stack[stack.length - 1]);
      to_heap && to_heap.size();
      to_heap = map.get(stack[stack.length - 1])
    ) {
      const to = to_heap.pop()!;
      stack.push(to);
    }

    const to = stack.pop()!;
    result.push(to);
  }
};

const getArrivalsByDeparture = (tickets: [Ticket, Ticket][]) => {
  const arrivals_by_departure = new Map<Ticket, Heap<Ticket>>();

  for (const [from, to] of tickets) {
    const to_heap = arrivals_by_departure.get(from) ?? new Heap<Ticket>('MIN');
    to_heap.push(to);
    arrivals_by_departure.set(from, to_heap);
  }

  return arrivals_by_departure;
};

class Heap<T>; // 힙 구현은 https://ha2el.tistory.com/23 참고

5. 풀이회고
직전에 푼 리트코드 문제와 완전히 동일한 문제이다.. 표절인가?

겸사겸사 기존에 풀었던 재귀 기반의 백트래킹 대신, 루프 기반의 백트래킹으로 리팩토링했다.

가능하면 백트래킹이 성능상 유리하고, 가능하면 루프가 성능상 유리하니.. 이렇게 짜는 게 제일 성능상 유리하겠지.

일단 끝까지 가서 -> 되돌아 나오는데 -> 갈림길 만날 때 까진 계속 끝이므로 (이미 엣지를 썼으니까) -> 백트래킹이 된다.

처음 짜보는 코드라 너무 헷갈려서 꽤 삽질했다. 이 정도로 이해하고 넘어가는 걸로 하자.