[DFS] 프로그래머스 '여행경로' - js

1. 문제

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

프로그래머스

2. 코드

처음 푼 코드)

처음에는 BFS를 사용하여 풀었고, 결과는 부분 통과였다. 이유는 '사전 순'이라는 조건만 구현해 주었기 때문이다.

이 문제의 주의할 점은 모든 공항을 방문해야 한다는 것이다! 그래서 이 문제는 BFS가 아니라 DFS로 푸는 문제였던 것이다.

만약, [["ICN", "a"], ["ICN", "b"], ["b", "ICN"]] 같은 경우에는 a에 먼저 가면 경로가 없으므로 b에 먼저 가야 하는 상황이 발생한다. 나는 이 부분을 경과한 것 탓에 부분 통과라는 결과를 받게 된 것이다.. 웬일로 내가 레벨 3 혼자 푸나 했어ㅠㅠ 혼자 있고 싶다..

function solution(tickets) {
    let links = {};
    let result = [];
    let queue = [];
    
    for(let i=0;i<tickets.length;i++){
        if(!links[tickets[i][0]]) links[tickets[i][0]] = [];
        links[tickets[i][0]].push(tickets[i][1]);
        links[tickets[0][0]].sort();
    }

    queue.push("ICN");
    result.push("ICN");
   
    while(queue.length){
      let airport = queue.shift();
      if(!links[airport] || !links[airport].length) break;
      queue.push(links[airport][0]);
      result.push(links[airport][0]);
      links[airport] = links[airport].slice(1);
    }
    
    return result;
}

정답)

가능한 모든 경우의 수를 계산하고 모든 공항을 방문하는 경로를 찾아 저장한 뒤, 후보 경로들을 정렬하여 나온 첫 번째 값을 리턴하면 정답이다. 정렬을 해야하는 이유는 예제 2에서 확인할 수 있다.

아래의 로직에서는 모든 공항을 다 방문한 경로만 answer에 저장하므로 위의 문제([["ICN", "a"], ["ICN", "b"], ["b", "ICN"]])도 해결된다.

 

dfs 파라미터

• airport : 현재 방문해야 하는 공항
• tickets : 모든 티켓을 다 써야하므로 엣지케이스 작성을 위해
• path : 공항 방문 경로

 

이 코드에서 집중해야 할 점은 dfs 함수 첫 줄에 있는 newPath 변수와 else문에 있는 copiedTickets 변수이다.

먼저 copiedTickets 변수부터 보자. 만약 원본 배열인 tickets를 복사하여 배열을 만든 후 splice하지 않고 ticktets에서 바로 splice를 진행한다면 모든 경로를 얻어낼 수 없다. 단지 배열 앞 쪽에 있는 ICN 출발 행 티켓을 사용하는 경로만 나올 뿐! 예를 들어 예제 2 같은 경우 ATL로 가는 경우도 계산해야 하지만 첫번째 요소가 splice 되어 처리가 불가능 해진다.

두번째로 newPath 변수이다. 만약 첫 번째 문장에서 newPath 변수를 선언하여 새로운 경로를 지정하지 않고 else 문 안에서 path에 push 한다면? 모든 경로가 맨 처음 선언되었던 path 파라미터 값인 '[]'에 담기는 바람에 배열 길이가 매우 길어질 것이다. 결론적으로, 각각의 경로 경우의 수에 따른 path를 저장하기 위해 dfs 함수 실행 후 경로에 대한 새로운 변수를 선언해주어, 뒤에서 다른 경로를 계산할 때 지장이 없게끔 만들어주는 것이다.

 

dfs/bfs 개념을 이해하고 유형을 파악하는 것도 중요하지만 이러한 부분들을 정확하게 알고 판단해야 문제를 맞출 수 있는 것 같다. 

function solution(tickets) {
  // 가능한 모든 경로 저장
  let answer = [];
  
  const dfs = (airport, tickets, path) => {
    // 경로
    let newPath = [...path, airport];
    // 모든 공항 다 방문한 경로만 answer에 저장
    if(tickets.length === 0){
      answer.push(newPath);
    }
    else{
      tickets.map((ticket, idx) => {
        if(ticket[0] === airport){
          // 방문한 경우 제거
          let copiedTickets = [...tickets];
          const [[from, to]] = copiedTickets.splice(idx, 1);
          dfs(to, copiedTickets, newPath)
        }
      });
    }
  };
    
  dfs("ICN", tickets, []);
  
  return answer.sort()[0];
}

다른 방법)

function solution(tickets) {
    // 최소 경로니까 bfs. 파라미터 : 현재 있는 공항, 경로, 남은 티켓
    // 모든 항공권을 사용하는 경우를 모아 알파벳 순으로 정렬
    let answer = [];
    let visited = new Array(tickets.length).fill(0);
    
    const bfs = (airport, visit) => {
        if(visit.length === tickets.length + 1){
            answer.push(visit);
            return;
        }else{
            for(let i=0;i<tickets.length;i++){
                if(tickets[i][0] === airport && !visited[i]){
                    visited[i] = 1;
                    let newV = visit.slice();
                    newV.push(tickets[i][1]);
                    bfs(tickets[i][1], newV);
                    visited[i] = 0;
                }
            }
        }
    }
    
    bfs("ICN", ["ICN"]);
    
    return answer.sort()[0];
}

 

+ 처음엔 문제 보고 bfs,dfs 구분도 못했고 스스로 로직도 못짜는 모습을 보며 마음이 정말 힘들었는데, 이제 내 스스로 파라미터를 생각해보고 직접 구현해보며 알고리즘 실력이 늘었다는게 눈에 보여 너무 신기하고 감사하다. 다시 한번 복기와 기록의 힘, 중요성을 느꼈다. 그리고 또 하나, 절때 꾸준함은 배신하지 않는다. 기적에는 시간이 무조건적으로 필요하다. 답답하고 걱정만 늘고 속상해서 놔버리고 싶을 때, 그 순간을 이기고 다시 한번 책상에 앉아 도전할 때 비로소 기적은 일어난다. 쉽게 얻어지는 것은 없다. 잊지말자. 내 자신 너무 기특하다!

 

복기

3/29
4/14