[프로그래머스] 여행경로

여행경로

---

1. 이해하기

• 주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다. 항상 "ICN" 공항에서 출발한다.
• 방문하는 공항 경로를 배열에 담아 출력한다.
• dfs문제이다.

---

2. 구현하기

• dfs(here,tickets,visited,tmp,answer,cnt): 현재 위치에서 tickets들을 살펴보면서 출발지가 현재위치이고 아직 방문하지 않은 곳을 방문한다. 이때 방문한다면 cnt를 1 증가시킨다. cnt가 모든 티켓의 수와 같다면 answer에 경로가 담긴 tmp값을 answer에 넣어주고 true를 반환한다.

  bool dfs(string here, vector<vector<string>>& tickets, vector<bool>& visited, vector<string>& tmp, vector<string>& answer, int cnt) {
      tmp.push_back(here);
      if(cnt == tickets.size()) {
          answer = tmp;
          return true;
      }
  
      for(int i = 0; i < tickets.size(); i++) {
          if(tickets[i][0] == here and !visited[i]) {
              visited[i] = true;
              if(dfs(tickets[i][1],tickets,visited,tmp,answer,cnt+1)) return true;
              visited[i] = false;
          }
      }
      tmp.pop_back();
      return false;
  }

• 방문을 할 때는 알파벳 순서대로 방문한다고 했으니 정렬을 시켜준다.

  sort(tickets.begin(),tickets.end());

---

3. 전체코드

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

using namespace std;

bool dfs(string here, vector<vector<string>>& tickets, vector<bool>& visited, vector<string>& tmp, vector<string>& answer, int cnt) {
    tmp.push_back(here);
    if(cnt == tickets.size()) {
        answer = tmp;
        return true;
    }

    for(int i = 0; i < tickets.size(); i++) {
        if(tickets[i][0] == here and !visited[i]) {
            visited[i] = true;
            if(dfs(tickets[i][1],tickets,visited,tmp,answer,cnt+1)) return true;
            visited[i] = false;
        }
    }
    tmp.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> visited(tickets.size(), false);

    sort(tickets.begin(),tickets.end());
    vector<string> tmp;
    dfs("ICN",tickets,visited,tmp,answer,0);
    return answer;
}

---

4. 총평

• 어려운 문제였다. 문자열 값을 이용해서 dfs를 풀어야 한다는 생각을 했을 때는 막막했으나 문자열을 이용하는 것이 아닌 tickets의 인덱스 값만 비교하면 된다는 것을 새로 알았다.