duck blog
Published on

프로그래머스 여행경로 (bfs/dfs)

Authors
  • avatar
    Name
    Deokgoo Kim
    Twitter

문제 풀이

bfs/dfs 분류의 문제입니다.
난이도는 중간 이라고 생각합니다.


문제 링크

function solution(tickets) {
  let answer = [];
  let visited = [];

  // 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
  // 따라서 sort를 진행하였습니다.
  tickets = tickets.sort((a, b) => {
    if (a[0] > b[0]) return 1;
    if (a[0] < b[0]) return -1;
    if (a[0] === b[0]) return a[1] > b[1] ? 1 : -1;
    return 0;
  });

  // 출발지가 contry가되며 아직 방문하지 않은 곳을 찾습니다.
  const getIndexFromStart = (contry) => {
    const res = [];
    tickets.forEach((x, idx) => {
      if (x[0] === contry && !visited[idx]) res.push(idx);
    });
    return res;
  };

  const dfs = (contry, level) => {
    const correctIndex = getIndexFromStart(contry);
    if (!correctIndex.length) return;
    while(correctIndex.length) {
      if(answer.length === tickets.length + 1) return;
      const idx = correctIndex.shift();
      const target = tickets[idx][1];
      answer[level] = target;
      visited[idx] = 1;
      dfs(target, level + 1);
      visited[idx] = 0;
    }
  };

  answer.push("ICN");
  dfs("ICN", 1);

  return answer;
}