[프로그래머스 LV 3](DFS) 여행경로

주어진 항공권을 모두 사용해서 여행경로를 만드는 문제 =>

DFS를 통해 그래프 처럼 그려가며 갈 수 있는 모든 경로를 방문하면서 정답에 추가해주면 될 것 같다.

다시 확인하고 넘어가는 DFS => 재귀함수로 구현 visited 를 사용하여 방문한곳 체크해주기!

그리고 알파벳 순서로 정렬-> 기본 sort사용 

기존코드(테스트 1,2번 실패)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[10001]={0};
vector<string> answer;
void dfs(vector<vector<string>> tickets,string ap){		//항공권과 현재공항
    answer.push_back(ap);			
    
    for(int i=0;i<tickets.size();i++){
        if(visited[i]) continue;			//방문한곳이면 continue;
        if(tickets[i][0]==ap){				//방문하지않은곳 중에
            visited[i]=true;				//방문처리				
            dfs(tickets,tickets[i][1]);		//연결된 다음공항으로 
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(),tickets.end());
    dfs(tickets,"ICN");				//시작은 언제나 ICN
    return answer;
}

 

 

1,2번이 실패했는데 

반례를 보니 

반례
    `입력`
    [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
    `정답`
    ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]

 

가다가 모든 항공권을 다 사용하지 않았는데 dfs함수가 끝나버리는 경우가 있어서 백트레킹이 필요하다고 한다.

백트레킹은 pop_back과 방문처리하는 배열을 통해 다시 할 수  있다.

 

고친 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[10001] = { 0 };
bool isall = false;			//항공권 다 사용했는 지 확인할 변수 
int ticketcnt = 0;			//항공권 사용한 횟수
vector<string> answer;
void dfs(vector<vector<string>> tickets, string ap) { //항공권, 현재 공항
    answer.push_back(ap);

    if (ticketcnt == tickets.size()) isall = true;          //항공권을 다 사용했다면
    for (int i = 0; i < tickets.size(); i++) {
        if (visited[i]) continue;                   //방문한곳이면 continue;
        if (tickets[i][0] == ap) {                  //방문하지않은곳 중에
            visited[i] = true;                      //방문처리
            ticketcnt++;                            //항공권사용수 증가
            dfs(tickets, tickets[i][1]);
            if (!isall) {                               //항공권 다 사용하지않았다면
                answer.pop_back();                      //백트레킹
                visited[i] = false;
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(), tickets.end());
    dfs(tickets, "ICN");                //시작은 언제나 ICN
    return answer;
}