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

 

코딩테스트 연습 - 여행경로

 

 

문제풀이

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다.

항상 "ICN" 공항에서 출발한다.

가능한 경로가 2개 이상일 경우에는 알파벳 순서가 앞서는 경로를 리턴한다.

주어진 항공권은 모두 사용해야 한다.

 

 

이 문제에서 주의해야 할 점은 주어진 항공권을 모두 써야한다는 것이다.

알파벳 순서가 앞서는 경로를 선택해서 갔을 때 항공권을 모두 사용하지 못하는 경우가 있다.

 

 

테케 하나를 예로 살펴보자.

 

[["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"],

["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]

 

"ICN" → "BOO" → "DOO" → "BOO" → "ICN"→"COO"까지는 알파벳 순서가 앞서는 경로를 따라간다면 쉽게 구할 수 있을 것이다.

 

이때 남아있는 티켓은 ["COO", "BOO"], ["COO", "DOO"], ["DOO", "COO"] 3개다.

알파벳 순서가 앞서는 경로를 따른다면 다음 공항은 "BOO"여야 한다.

 

하지만 "BOO" 공항으로 가면 남은 ["COO", "DOO"], ["DOO", "COO"] 티켓을 쓰지 못한다.

"BOO" 공항에서 "COO" 공항이나 "DOO" 공항으로 갈 수 없기 때문이다.

그래서 이때는 알파벳 순서가 앞서는 "BOO"보다 "DOO" 공항으로 가야 남은 티켓을 모두 쓸 수 있다.

 

 

 

모든 티켓을 쓰는 경로를 찾기 위해서 dfs를 bool 타입으로 선언해주었고 모든 티켓을 다 쓴 경우, 즉 cnt == n인 경우에 탐색을 종료하도록 코드를 짰다.

 

다음에 방문할 공항을 찾기 위해 tickets[i][0]이 현재 있는 공항인 티켓을 찾아서 모두 next 벡터에 저장해둔다.

알파벳 순서대로 정렬한 후에 각 티켓을 써보고 모든 티켓을 다 쓴 경로를 찾을 경우 종료해준다.

 

 

C++ 코드

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	int n;
	vector<bool> visited; // 티켓 사용 여부
	vector<string> answer; // 방문하는 공항 경로
	bool cmp(pair<int, string> a, pair<int, string> b) {
	return a.second < b.second;
	}
	bool dfs(vector<vector<string>>& tickets, string now, int cnt) {
	if (cnt == n)
	return true;
	// 다음 공항 후보 탐색
	vector<pair<int, string>> next;
	for (int i = 0; i < n; i++) {
	// 현재 공항에서 갈 수 있는 경로 중 아직 티켓을 쓰지 않은 곳을 찾는다
	if (tickets[i][0] == now && !visited[i]) {
	next.push_back({ i, tickets[i][1] });
	}
	}
	// 알파벳 순서대로 정렬
	sort(next.begin(), next.end(), cmp);
	for (pair<int, string> nxt : next) {
	visited[nxt.first] = true;
	answer.push_back(nxt.second);
	// 모든 항공권을 사용하여 여행경로를 짰으면 종료
	if (dfs(tickets, nxt.second, cnt + 1))
	return true;
	visited[nxt.first] = false;
	answer.pop_back();
	}
	return false;
	}
	vector<string> solution(vector<vector<string>> tickets) {
	n = tickets.size();
	visited.resize(n);
	answer.push_back("ICN");
	dfs(tickets, "ICN", 0);
	return answer;
	}

view raw [프로그래머스] 여행경로.cpp hosted with ❤ by GitHub