프로그래머스 레벨3 여행경로

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

 

서론

DFS+완전탐색+백트래킹을 이용해서 구현

---

풀이

이동가능한 모든 경로를 DFS+완전탐색으로 구현하는데, 현재 항공권의 도착지가 다음 항공권의 출발지와 같을 수 있도록 백트래킹을 추가

 

여행의 출발은 무조건 ICN이다. tickets중 출발지가 ICN을 찾아서 DFS를 시작한다.

for (int i = 0; i < ticketNum; i++) {
	if (tickets[i][0].compare("ICN") == 0) {
		dfs(...);
	}
}

 

현재 항공권의 도착지와 다음 항공권의 출발지가 같으며 아직 사용하지 않은 항공권일때 DFS를 이어간다.

항공권의 사용여부를 파악하는 이유는 예제2번의 ['ICN", "ALT"], ["ALT", "ICN"]에서 두 공항이 무한루프를 돌 수 있기 떄문이다.

DFS의 파라미터 중 sum 문자열에 방문하는 공항이 계속 추가되어 여행경로가 갱신된다.

void dfs(int depth, int index, string sum, vector<vector<string>> &tickets) {

	...
    
	visited[index] = 1; // 항공권 사용처리
	for (int i = 0; i < ticketNum; i++) {
		if (visited[i] == 0 && tickets[index][1] == tickets[i][0]) {
			dfs(depth + 1, i, sum + tickets[i][0], tickets);
		}
	}
	visited[index] = 0;
	return;
}

 

모든 항공권을 다 사용했으면 현재 여행경로를 이전에 저장했던 여행경로 변수와 알파벳순으로 비교해서 여행경로 변수에 저장할지 말지 결정한다. 

void dfs(int depth, int index, string sum, vector<vector<string>> &tickets) {
	if (depth == ticketNum) {
		sum += tickets[index][1];
        // 여행경로 변수는 answerTmp이며 최초에는 공백으로 선언되어 있어서 알파벳 순으로 정렬하면 1등이다. 그래서 공백일때는 알파벳체크를 하지 않는다.
		if (answerTmp.compare("") == 0 || answerTmp.compare(sum) > 0) { 
			answerTmp = sum;
		}
		return;
	}

	...

}

 

DFS가 끝나면 여행경로 변수를 answer에 넣어준다.

현재 저장된 여행경로 변수는 "ICNJFKHNDIAD"와 같이 토크나이저가 없으므로 앞에서부터 3개씩 끊어준다.

for (int i = 0, len = answerTmp.length(); i < len; i += 3) {
	string tmp = "";
	tmp += answerTmp[i];
	tmp += answerTmp[i + 1];
	tmp += answerTmp[i + 2];
	answer.push_back(tmp);
}

 

---

구현

// C++

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int visited[10000];

string answerTmp;

int ticketNum;
void dfs(int depth, int index, string sum, vector<vector<string>> &tickets){
    if(depth == ticketNum) {
        sum += tickets[index][1];
        if(answerTmp.compare("") == 0 || answerTmp.compare(sum) > 0){
            answerTmp = sum;
            cout<<depth<<" "<<sum<<endl;
        }
        return;
    }
    
    visited[index] = 1;

    for(int i=0;i<ticketNum;i++){
        if(visited[i] == 0 && tickets[index][1] == tickets[i][0]){
            dfs(depth+1, i, sum+tickets[i][0], tickets);
        }
    }
    
    visited[index] = 0;
    return;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    
    ticketNum = tickets.size();
    for(int i=0;i<ticketNum;i++){
        if(tickets[i][0].compare("ICN") == 0){
            dfs(1, i, "ICN", tickets);
        }
    }
    
    for(int i=0, len = answerTmp.length();i<len;i+=3){
        string tmp = "";
        tmp += answerTmp[i];
        tmp += answerTmp[i+1];
        tmp += answerTmp[i+2];
        answer.push_back(tmp);
    }
    
    return answer;
}