327. 여행경로

프로그래머스

1. Python

from collections import defaultdict
def solution(tickets):
    def dfs(now, answer):
        if len(answer) == len(tickets) + 1: #주어진 항공권은 모두 사용해야 합니다.
            return answer

        for i, v in enumerate(routes[now]):
            routes[now].pop(i)
            temp = answer[:] 
            temp.append(v)
            ret = dfs(v, temp)
            if ret: return ret 
            routes[now].insert(i, v) 

            
    routes = defaultdict(list)
    
    for a, b in tickets:
        routes[a].append(b)
    
    for r in routes:
        routes[r].sort()

    return dfs("ICN", ["ICN"])

  

2. C++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int max_cnt = 0;

void dfs(string start, vector<vector<string>>& tickets, vector<bool>& visit, vector<string>& answer, vector<string>& temp, int cnt) {
    temp.push_back(start);
    
    if (max_cnt < cnt) {
        max_cnt = cnt;
        answer = temp;
    }
    
    for (int i = 0; i < tickets.size(); i++) {
        if (start == tickets[i][0] && !visit[i]) {
            visit[i] = 1;
            dfs(tickets[i][1], tickets, visit, answer, temp, cnt + 1);
            visit[i] = 0;
        }
    }
    temp.pop_back();
}

vector<string> solution(vector<vector<string>> tickets) {
    int cnt = 0;
    vector<string> answer, temp;
    vector<bool> visit(tickets.size(), 0);
    sort(tickets.begin(), tickets.end());
    dfs("ICN", tickets, visit, answer, temp, cnt);
    return answer;
}

3. JavaScript

function solution(tickets) {
  let answer = [];
  const result = [];
  const visited = [];
  tickets.sort();
    
  function dfs(str, count){
    result.push(str);
    if(count === tickets.length) {
      answer = result;
      return true;
    }
    
    for(let i = 0; i < tickets.length; i++) {
      if(!visited[i] && tickets[i][0] === str) {
        visited[i] = true;
        if(dfs(tickets[i][1], count+1)) return true;
        visited[i] = false;
      }
    }
    
    result.pop();
    return false;
  }
  
  dfs("ICN", 0);
  
  return answer;
}