<Programmers> DFS/BFS_여행 경로(Travel Route) c++

여행 경로 문제 링크

문제를 보면 a공항에서 b공항으로, b공항에서 c공항으로 가는 항공권이 있을 때 a,b,c 순서대로 출력해야 한다.
DFS를 사용하여 문제를 풀고, 주어진 항공권은 모두 사용해야 하므로 모든 tickets의 정점을 방문해야 한다

1. 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞에 있는 값을 return 해야 하므로 tickets을 먼저 정렬

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

2. DFS 함수

string cur, vector<vector<string>> &tickets, 
vector<bool> &visited, vector<string>& answer, int usedNum

현재 출발 항공권을 cur, 이때까지 사용한 항공권의 개수 usedNum, 항공권을 순서대로 저장할 answer을 인자로 넘긴다

3. DFS 함수의 true 종료 조건은

if (usedNum==tickets.size()) return true

사용한 항공권의 개수와 전체 티켓의 개수가 같을 때

4. 현재 항공권과 나머지 항공권의 출발지 (tickets[i][0])가 같고, 이 출발지가 한 번도 방문된 적 없을 때 DFS를 다시 호출한다. 이때 현재 항공권은 나머지 항공권의 도착지 (tickets[i][1])이고, 사용한 항공권의 개수 (usedNum)에 1을 더해주어 넘겨준다.

   DFS를 호출한 뒤 결과가 true이면 true를 리턴하고 끝낸다
   아니면 현재를 다시 미방문으로 표시하고 다시 탐색한다.

    for (int i=0; i<tickets.size(); i++) {
        if (cur==tickets[i][0] && !visited[i]) {
            visited[i]=true;
      	    bool check=DFS(tickets[i][1], tickets, visited,
        		answer, usedNum+1);
            if (check) return true;
            visited[i]=false;
        }
    }

소스코드

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

using namespace std;

bool DFS(string cur, vector<vector<string>> &tickets, vector<bool> &visited, vector<string>& answer, int usedNum) {
  
    answer.push_back(cur);
    if (usedNum==tickets.size()) return true;
   
    for (int i=0; i<tickets.size(); i++) {
        if (cur==tickets[i][0] && !visited[i]) {
            visited[i]=true;
           
        bool check=DFS(tickets[i][1], tickets, visited, answer, usedNum+1);
           
            if (check) return true;
            visited[i]=false;
        }
    }
    answer.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());
  
    DFS("ICN", tickets, visited, answer, 0);
 
    return answer;
}