1. 여행경로

여행경로를 알아내는 프로그램을 작성해야한다. 어디서 출발하며 어디를 거쳐 어디에 도착해야할지 알아내야한다. 우선 항상 ICN에서 출발한다. 그리고 ICN에 도착해서 도착지에서 출발할 수 있는 장소를 이어서 출력하면 된다. 그리고 출발지에서 갈 수 있는 곳이 2군데 이상이라고 한다면 알파벳 순서대로 가도록 한다.

그리고 당연히 갔던 곳은 못간다. 그럼 아래와 같은 티켓이 주어졌을 때 다음과 같은 경로가 출력이 된다.

let flight1 = [
  ["ICN", "JFK"],
  ["HND", "IAD"],
  ["JFK", "HND"],
];
// [("ICN", "JFK", "HND", "IAD")]

let flight2 = [
  ["ICN", "ATL"],
  ["ICN", "SFO"],
  ["SFO", "ATL"],
  ["ATL", "ICN"],
  ["ATL", "SFO"],
];
// [("ICN", "ATL", "ICN", "SFO", "ATL", "SFO")];

2. 접근 방법

일단 다음값으로 넘어가는 식이므로 queue를 써야할 것 같다. 그럼 BFS를 써야겠지?

• pseudo code
  • tickets을 sort한다
  • ICN을 찾아서 Q에 담는다
  • WHILE을 돌린다
    • Q에서 뽑아서 DEP / DES에 할당한다
    • DEP에 해당되는 TICKET을 없앤다
    • DES에 해당되는 TICKET을 Q에 추가한다.
    • Q에 아무것도 없을때 까지 반복한다.

function mySolution(tickets) {
  tickets.sort();

  let answer = [];

  let q = [
    tickets.find((ticket) => {
      return ticket[0] === "ICN";
    }),
  ];

  while (q.length) {
    let [dep, des] = q.shift();
    for (let ind in tickets) {
      if (tickets[ind][0] === dep) {
        tickets.splice(ind, 1);
        break;
      }
    }

    answer.push(dep);

    for (let idx in tickets) {
      if (tickets[idx][0] === des) {
        q.push(tickets[idx]);
        break;
      }
    }

    if (q.length === 0) answer.push(dep);
  }

  return answer;
}

테스트케이스는 다 맞았는데 최종케이스는 반은 맞고 반은 틀렸다..ㅋㅋㅋ

그래서 답을 보았다.

let visit
let answer

const dfs = (tickets,start,res,cnt) => {
  res.push(start)

  if(cnt === tickets.length) {
    answer = res
    return true
  }

  for(let i = 0; i<tickets.length;i++) {
    if(visit[i] === 0 && tickets[i][0] === start) {
      visit[i] = 1

      const result = dfs(tickets, tickets[i][1], res, cnt+1)

      if(result) return true

      visit[i] = 0
      res.pop()
    }

  }
  return false
}

function otherSolution(tickets) {
  const arr = [...tickets].sort()
  visit new Array(tickets.lengt).fill(0)

  dfs(arr,'ICN',[],0)

  return answer
}

let flight3 = [
  ['ICN', 'ATL'],
  ['ICN', 'SFO'],
  ['SFO', 'ICN'],
];

bfs가 아닌 dfs를 써야하는 구나!

역시 간단하면서 효율적이다. 현답은 단순하고 명쾌하구나!!

많이 돌려보고 생각해보니깐 이제 이해된다. visit을 만든다. 근데 visit에 항공사 이름을 key로 입력하는게 아닌 ticket안에서의 위치를 보고 mark한다. 즉 idx로 mark한다는거 그리고 방문안했으면서 목적지인 ticket을 뽑아서 dfs들어간다. 이때 result 배열에다가 누적시키면서 넘겨준다. 그리고 마지막으로 cnt를 넘겨주는데 cnt는 내가 얼마나 티켓을 뽑았느냐를 check 한다. 그리고 티켓을 5개 뽑았을때 (cnt===tickets.length) return true한다. 그럼 그 뒤 for문에서 남은 불필요한 반복이 모두 취소가 된다.

그리고 마지막에 return false인 이유는 flight3를 염두해두고 언급하신것 같다.

flight3를 한 번 실행해보자!

목적지에 도착했는데 그 목적지에서 출발하는 티켓이 없을 경우를 의미한다. 그래서 다시 돌아와서 dfs가 끝났을 때 if(result) 에 안걸리게 되고 visit되었고 RESULT에서도 빠지게 된다. 그러고 나서 SFO에 들리고 다시 ICN에 들른다음 마지막에 ATL에 들리게 된다. 그러면서 ATL은 마지막에 RESULT에 추가가 되는 것이다. 여러가지 장치가 들어갔다. visit + result + cnt. 이 장치가 유기적으로 돌아가는 모습이 참 신기하고 보기좋다.

3. 배운점

1. bfs와 dfs의 차이점은 뭔가. bfs는 뭔가 조건이 안맞을때까지 계속 반복할 수 있는것이 아닐까? while처럼. q에 계속 뭔가를 추가하는 거니깐. 반면 dfs는 어느 길이가 되면 return하고 함수가 끝나게 된다. 여행경로도 모든 티켓을 다 쓰면 dfs가 끝나는 것 처럼 말이다.

2. 누적해서 넘기는 법이 인상깊다.

3. dfs에 return값을 주고 그걸 이용해서 불필요한 반복을 줄였다

4. visit에다가 key를 ticket의 이름을 추가하는 것이 아닌 idx를 이용해서 mark하는게 인상깊었다.

5. 목적지가 출발지인 티켓이 없는 예외의 경우를 잘 파악했다.