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

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

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

 

여러 공항이 있고, 출발지와 도착지가 적힌 티켓이 tickets 배열에 주어집니다.

Tickets 내의 모든 티켓들을 각각 한 번씩만 사용하여, 주어진 모든 도시를 방문하는 경우의 방문 순서를 구하는 문제입니다.

모든 도시를 방문할 수 없는 경우는 입력으로 주어지지 않으며, 가능한 경우가 여러 가지 존재하는 경우, 알파벳 순으로 가장 앞서는 하나의 경우를 답으로 return합니다.

 

DFS (깊이 우선 탐색)을 통해 접근하였습니다.

구현의 편리함을 위해 재귀함수를 이용하였고, 매 방문 시마다 사용한 티켓을 체크하고, 방문한 경로에 추가한 후, 다음 함수에 넘기는 방법으로 접근하였습니다.

방문한 도시의 숫자는 티켓의 수 + 1이어야 하므로, 접근할 수 있는 도시가 없고 방문한 도시의 숫자가 조건을 만족하는 경우 answer_candidates 배열에 추가합니다.

탐색을 마친 후, 가능한 경로가 여러 개 존재할 경우, 이를 문제의 조건에 맞게 정렬합니다. 정렬을 위해 ans_sort 함수를 별도로 작성하였습니다.

이후 answer_candidates의 맨 앞 원소를 답으로 return하면 됩니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector <vector <string> > answer_candidates;
	bool strcmp(string st1, string st2) {
	if (st1.size() != st2.size()) return false;
	for (int i = 0; i < st1.size(); i++) {
	if (st1[i] != st2[i]) return false;
	}
	return true;
	}
	bool ans_sort (vector <string> st1, vector <string> st2) {
	for (int i = 0; i < st1.size(); i++) {
	if (strcmp(st1[i], st2[i])) continue;
	return st1[i] < st2[i];
	}
	}
	void bfs (vector<vector<string> > &tickets, vector<bool> visited, vector<string> visited_list, string current_city) {
	vector<int> can_visit_list;
	for (int i = 0; i < tickets.size(); i++) {
	if (strcmp(tickets[i][0], current_city) && !visited[i]) {
	can_visit_list.push_back(i);
	}
	}
	if (can_visit_list.empty()) {
	if (visited_list.size() == tickets.size() + 1) {
	answer_candidates.push_back(visited_list);
	}
	return;
	}
	for (auto &next : can_visit_list) {
	visited[next] = true;
	visited_list.push_back(tickets[next][1]);
	bfs(tickets, visited, visited_list, tickets[next][1]);
	visited[next] = false;
	visited_list.pop_back();
	}
	}
	vector<string> solution(vector<vector<string>> tickets) {
	vector<string> answer;
	answer.push_back("ICN");
	vector<bool> visited(tickets.size(), false);
	bfs(tickets, visited, answer, "ICN");
	sort(answer_candidates.begin(), answer_candidates.end(), ans_sort);
	answer.clear();
	answer.assign(answer_candidates[0].begin(), answer_candidates[0].end());
	return answer;
	}

view raw 여행경로.cpp hosted with ❤ by GitHub

채점 결과

테스트 케이스가 달랑 4개라서... 잘 풀었는지 모르겠네요.

DFS를 이용하는 적당한 난이도의 문제였던 것 같습니다.