[프로그래머스 / C++] 여행경로

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

문제풀이

1. 처음엔 인접행렬을 어떻게 만들어주지..? 하다가 꼬였다.
   dfs에 시작점 인자(string)를 보내고, dfs내에서 tickets 배열을 돌면서 첫번째 열 요소가 현재 시작점과 같으면 두번재 열 요소인 도착점으로 경로를 보내면 된다.

2. 모든 티켓을 사용해야하므로, dfs level이 tickets.size()와 같아질 때 종료한다.

3. 정렬을 하고 나서 경로를 찾는데, 한 번 경로를 찾았으면 더 이상 찾을 거 없이 종료해야 한다는 것! bool dfs를 이용해 구현하였다.

4. answer는 vector형라서 도착점을 뒤에 push_back하면서 경로를 만들어주었다. 따라서 백트래킹 했을 경우 pop_back을 해주어야함!

코드

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

using namespace std;

bool visited[100001];
vector <string> answer;

bool dfs(int l,string start,vector<vector<string>> tickets){
    //모든 경로를 탐색했을 경우
    if(l==tickets.size()){
        return true; 
    }

    for(int i=0;i<tickets.size();i++){
        if(start==tickets[i][0]&&!visited[i]){ //start가 갈 수 있는 곳 중 방문하지 않은 경로
            visited[i]=1;
            answer.push_back(tickets[i][1]);
            bool check=dfs(l+1,tickets[i][1], tickets);
            if(check) return true; // 하나라도 탐색을 더 이상 탐색 안 함 return
            visited[i]=0;
            answer.pop_back();
        }
    }
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(),tickets.end()); // 알파벳 순서가 앞서는 경로로     
    
    //인천부터 시작
    answer.push_back("ICN");
    dfs(0,"ICN", tickets);
    
    return answer;
}