61. 여행경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164?itm_content=course14743 

프로그래머스

[문제설명]

문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다.
항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때,
방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력
tickets [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
return ["ICN", "JFK", "HND", "IAD"]

[ 문제 풀이 ]

 

첫번째 풀이 

function solution(tickets) {
  const answer = [];
  
  // 그래프를 생성하고 각 공항별로 티켓을 정렬합니다.
  const graph = {};
  for (const [from, to] of tickets) {
    if (!graph[from]) {
      graph[from] = [];
    }
    graph[from].push(to);
  }
  
  // 각 공항의 티켓을 알파벳 순으로 정렬합니다.
  for (const from in graph) {
    graph[from].sort();
  }
  
  // DFS 함수를 정의합니다.
  function dfs(node) {
    if (answer.length === tickets.length + 1) {
      return true; // 모든 티켓을 사용한 경우 종료
    }
    
    if (!graph[node]) {
      return false; // 더 이상 갈 수 있는 공항이 없는 경우 종료
    }
    
    for (let i = 0; i < graph[node].length; i++) {
      const next = graph[node][i];
      graph[node].splice(i, 1); // 사용한 티켓 제거
      answer.push(next);
      if (dfs(next)) {
        return true;
      }
      answer.pop();
      graph[node].splice(i, 0, next); // 백트래킹
    }
    
    return false; // 가능한 경로를 찾지 못한 경우 종료
  }
  
  answer.push("ICN"); // 출발 공항은 항상 ICN
  
  dfs("ICN");
  
  return answer;
}

 

1. 그래프를 생성하고 각 공항별로 티켓을 정렬해주자

const graph ={};

[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]

어떻게?

ICN: ['SFO','ATL'], ATL: ['ICN','SFO'], SFO: ['ATL'] 이런식으로

 

 

2. from 공항을 키를 갖는 그래프가 아직 없다면, 빈배열을 할당, 그리고 to 공항 값을 넣어준다.

for (const [from, to] of ticket) {
  if (!graph[from]) {
    graph[from] = [];
  }
  graph[from].push(to);
}

반복문에 const [from, to](배열 디스트럭처링)을 써볼 생각을 하지않았다.

 

배열 디스트럭처링 (Array Destructuring)

: 배열에서 원소들을 추출하여 개별 변수로 할당하는 문법적 기능

 

 

3. 각 티켓을 알파벳 순으로 배치

  for (const from in graph) {
    graph[from].sort();
  }

4. 모든 티켓을 모든 사용한 경우

  if (answer.length === tickets.length + 1) {
      return true; 
    }

5. 더 이상 갈 곳이 없다면 종료

  if (!graph[node]) {
    return false;
  }

 

6.현재 공항에서 갈 수 있는 다음 공항들에 대한 루프를 시작

for (let i = 0; i < graph[node].length; i++) { … }

7. 다음으로 이동할 공항을 next 변수에 저장

const next = graph[node][i];

8. 현재 공항에서 next로 이동하는 항공권을 사용했으므로, 그래프에서 이 항공권을 제거

graph[node].splice(i, 1);

9. next 공항을 방문 경로에 추가

answer.push(next);

10.  dfs(next)를 호출하여 다음 공항에서부터의 경로 탐색

if (dfs(next)) { return true; }

만약 가능한 경로가 있다면 true를 반환하고, 현재 경로에서도 true를 반환하여 종료합니다.

 

11. 현재 경로에서 next를 방문한 것이 실패했거나 백트래킹을 위해 next를 방문 경로에서 제거

answer.pop();

12. 백트래킹을 위해 사용한 항공권을 그래프에 다시 추가

graph[node].splice(i, 0, next);

return false;: 현재 공항에서 모든 가능한 경로를 시도해 보았지만, 

가능한 경로를 찾지 못한 경우 false를 반환하여 종료

 

진짜 어렵네..