[Programmers] Lv3. 여행경로

• 이 문제는 C++로 풀이를 작성하였습니다.

문제

예제

---

풀이

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <utility>
	using namespace std;
	bool check=false; // 최소 판단 변수
	vector<string> answer; // 답이 될수 있는 벡터
	vector<string> result; // 정답을 가지고 있는 벡터
	// 알파벳 순서가 앞서는 경로부터 탐색하기 위한 비교함수
	bool cmp(pair<string,int> a,pair<string,int> b){
	return a.first<b.first;
	}
	// 탐색 dfs
	void dfs(string str,vector<int>& v, vector<vector<string>>& tickets){
	bool flag=true;
	for(int i=0;i<v.size();i++){
	if(v[i]==0){
	flag=false;
	}
	}
	if(flag){
	if(!check){
	for(int i=0;i<answer.size();i++){
	result.push_back(answer[i]);
	check=1;
	}
	}
	return;
	}
	vector<pair<string,int>> data;
	for(int i=0;i<v.size();i++){
	if(tickets[i][0]==str && v[i]==0){
	data.push_back(make_pair(tickets[i][1],i));
	}
	}
	sort(data.begin(),data.end(),cmp);
	for(int i=0;i<data.size();i++){
	pair<string,int> p=data[i];
	answer.push_back(p.first);
	v[p.second]=1;
	dfs(p.first,v,tickets);
	v[p.second]=0;
	answer.pop_back();
	}
	}
	// ICN부터 시작해서 ICN의 문자열을 가지고 있는 벡터를 찾기
	// ICN시작해서 도착하는 공항을 벡터에 담아 알파벳순으로 정렬
	// 가장 앞부분의 공항으로 출발하여 모든 공항을 탐색할 경우 해당 답 출력
	// 중요!! 가장 어려웠던 점 : 해답 answer을 어떻게 얻을 것인가?
	// 나는 전역변수로 풀었지만, 좋은 답안으로 알파벳이 크기가 무조건 3이므로 string에 넣어 3문자씩 끊어서 읽기
	// string은 크기비교도 되기 때문에 answer, result로 나눌 필요도 없다
	vector<string> solution(vector<vector<string>> tickets) {
	vector<int> v(tickets.size(),0);
	answer.push_back("ICN");
	dfs("ICN",v,tickets);
	return result;
	}

view raw Programmers Lv3.travel path.cpp hosted with ❤ by GitHub

• 추가로 궁금한 점이나 수정할 사항 있으면 댓글로 남겨주세요.