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

문제 링크

여행경로

풀이

DFS로 푸는 문제

1. map에 key는 출발 도시, value는 도착 도시들이 들어간다. 방문했는지를 판단하기 위해 pair로 정의한다.
   1-1. 경로가 여러개 일 경우 알파벳 순으로 하니 오름차순 정렬을 해준다.
2. 재귀를 이용한 DFS를 하는데, 현재 경로의 사이즈가 티켓의 사이즈+1일 경우 answer에 값이 없으면 return 한다.
   2-1. map의 value값을 돌면서 m[cur][i].second==1인 경우는 방문한 경우라 continue, 아니라면 방문 표시와 현재 경로 갱신 후 다시 재귀 호출한다.

코드

#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

vector<string> answer;
int ticketsSize;

void DFS(map<string, vector<pair<string, int>>> &m, string cur, vector<string> curPath)
{
    if(curPath.size()==ticketsSize+1) 
    {
        if(answer.empty()) answer = curPath;
        return;
    }
	for (int i=0;i<m[cur].size();i++)
	{
		if (m[cur][i].second == 1) continue;
        
        map<string, vector<pair<string, int>>> tmpMap = m;
		tmpMap[cur][i].second = 1;
        
        vector<string> tmpPath = curPath;
        tmpPath.push_back(tmpMap[cur][i].first);
        
		DFS(tmpMap,tmpMap[cur][i].first, tmpPath);
	}
}

vector<string> solution(vector<vector<string>> tickets) {
	map<string, vector<pair<string, int>>> m;
    ticketsSize = tickets.size();

	sort(tickets.begin(), tickets.end());

	for (int i = 0; i < tickets.size(); i++)
	{
		m[tickets[i][0]].push_back({ tickets[i][1],0 });
	}
    
	DFS(m, "ICN",{"ICN"});
    
    return answer;
}