[프로그래머스/알고리즘] 여행경로 알고리즘

프로그래머스

문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. ex)

tickets :[[ICN, JFK], [HND, IAD], [JFK, HND]]

 return : [ICN, JFK, HND, IAD]

해결 과정

처음에 생각했던 것은 map에다 저장을 해서 풀어나가려고 했다.

출발지점	도착지점
ICN	JFK
HND	IAD
JFK	HND

위와 같이 출발지점은 Key이고 도착지점은 Value로 지정해서 저장한다. 도착지점은 여러개 일수 있다. (인천에서 서울, 서울에서 인천으로 왔다가 인천에서 미국 갈수 있다) ---> 도착지점을 deque으로 저장(우선순위 큐가 좀더 좋아보이지만 이걸로 했다) 제한사항에서 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 한다. 이를 해결하기 위해 그냥 도착지점 각각을 sort함수로 정렬했다. 그래서 ICN출발하면 도착지점의 0번째 인덱스부터 방문을 하고 방문을 했으면 제거하면 된다.  0번째 인덱스는 JFK이므로 ICN 도착지점은 null이 되고, JFK의 0번째를 방문해서 HND을 방문 후 제거 이렇게 반복하면 된다. 하지만 프로그래머스에서 알려주지 않았던 테스트 케이스가 존재한다. -> 바로 사이클이 생겼을 때 오류가 생긴다.

(F->A)로 연결하는 걸 안넣었네요

여기서 A가 ICN이라고 생각하자 먼저 A->B->C를 이동하고 다시 A로 돌아올 때 A는 D하고 E로 갈 수 있는데 알파벳 순서로 D로 이동을 하면 E, G, F 가 방문을 할 수 가 없다. 이런 사이클 문제를 해결하기 위해서 어쩔 수 없이 DFS를 사용해야 한다. DFS를 이용해서 알파벳이 먼저 앞서는 순서부터 해당 지역의 모든 이동을 탐색을 해서 발견하면 알고리즘이 종료가 된다.

소스코드
 

#include <string>
#include <vector>
#include <map>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
vector<string> dfs(map<string, deque<string>> m, vector<string> p, int j, int allsize,string prev, string next,int k);

vector<string> solution(vector<vector<string>> tickets) {
	vector<string> answer;
	map<string, deque<string>> m;
	map<string, deque<string>>::iterator iter;

	for (int i = 0; i < tickets.size(); i++) {
		iter = m.find(tickets[i][0]);
		if (m.find(tickets[i][0]) == m.end())
		{
			deque<string> temp;
			temp.push_back(tickets[i][1]);
			m.insert({ tickets[i][0], temp });
		}
		else {
			deque<string> temp = iter->second;
			temp.push_back(tickets[i][1]);
			m[tickets[i][0]] = temp;
		}
	}

	for (iter = m.begin(); iter != m.end(); ++iter)
		sort((iter->second).begin(), (iter->second).end());

	return dfs(m,answer,0,tickets.size(),"","ICN",0);
}

vector<string> dfs(map<string, deque<string>> m_, vector<string> p,int j,int allsize,string prev, string next,int k) {
	map<string, deque<string>> m = m_;
	deque<string>::iterator iter = m[prev].begin();
	vector<string> answer = p;
	vector<string> temp;
	if (prev != "") {
		//m[prev].pop_front();
		m[prev].erase(iter + k);
	}
		
	answer.push_back(next);
	prev = next;
	if (m[next].empty())
		return answer;
	for (int i = 0; i < m[next].size(); i++) {
		temp=dfs(m, answer, j + 1, allsize, prev, m[next][i],i);
		if (temp.size() == allsize+1)
			return temp;
	}
	return answer;
}