프로그래머스 여행 경로

https://programmers.co.kr/learn/courses/30/lessons/43164

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

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
   vector<string> answer;
   int visit[10001] = { 0, };
   int endCnt = 0;//전체 배열 방문하면 종료 위한 변수
   sort(tickets.begin(), tickets.end());
   int startIdx = 0;//시작하는 인덱스

   for (int i = 0; i < tickets.size(); i++) {//icn 검출하는 코드
      if (tickets[i][0] == "ICN") {
         startIdx = i;
         endCnt++;
         break;
      }
   }

   answer.push_back(tickets[startIdx][0]);
   visit[startIdx] = 1;//중복 체크

   while (1) {
      if (endCnt == tickets.size()) {
         answer.push_back(tickets[startIdx][1]);
         break;
      }
      for (int i = 0; i < tickets.size(); i++) {
         if (visit[i] == 0 && (tickets[startIdx][1] == tickets[i][0])) {
            visit[i] = 1;
            endCnt++;
            startIdx = i;
            answer.push_back(tickets[i][0]);//경로 저장v
            break;
         }
      }
   }
   return answer;
}

일차원적으로 풀게 되면 무조건 시간초과가 생깁니다. 그래서 알고리즘 기법을 활용하는것이죠

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<queue>
#include<map>
using namespace std;
int visit[10001];
void dfs(string startC, vector<vector<string>> &tickets, vector<string> &answer) {
   answer.push_back(startC);//경로 저장
   for (int i = 0; i < tickets.size(); i++) {
      if (startC == tickets[i][0] && visit[i] == 0) {//출발점을 찾아서 배열 체크 
         visit[i] = 1;
         dfs(tickets[i][1], tickets, answer);
      }
   }
}
vector<string> solution(vector<vector<string>> tickets) {
   vector<string> answer;
   int endCnt = 0;//전체 배열 방문하면 종료 위한 변수
   sort(tickets.begin(), tickets.end());
   dfs("ICN", tickets,answer);//출발 위치, 여행지 정보, 여행 경로 



   return answer;
}
int main(void) {
   vector<string> a;
   //a = solution({ {"ICN", "JFK"},{"HND", "IAD"},{"JFK", "HND"} });
   a = solution({ {"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"}});
   for (int i = 0; i < a.size(); i++) {
      cout << a[i] << " ";
   }
   cout << endl;
   return 0;
}

 

 

dfs 로 경로를 찾아가자 했는데 실패가 두개 가 나오네요 확실히 시간은 줄였습니다. 

흠 여기서 생각해본결과 전체가 경로를 가지 않은경우에 출력이되는것 같아요 

그래서 그경우를 걸러줘야합니다. 즉, 모든 경로를 가고 나서 출력이라는것이

위에 소스에서 빠진것이죠 

 

그래서 이런식으로 바꿔봤습니다. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<queue>
#include<map>
using namespace std;
int visit[10001];
int flag = 0;
int dfs(string startC, vector<vector<string>> &tickets, vector<string> &temp, vector<string> &answer,int cnt) {
	temp.push_back(startC);
	if (cnt == tickets.size())
	{
		answer = temp;
		return 1;
	}
	for (int i = 0; i < tickets.size(); i++) {
		if (startC == tickets[i][0] && visit[i] == 0) {//출발점을 찾아서 배열 체크 
			visit[i] = 1;
			int a= dfs(tickets[i][1], tickets,temp, answer,cnt+1);
			if (a == 1) return 1;
			visit[i] = 0;
		}
	}
	temp.pop_back();
	return 0;
}
vector<string> solution(vector<vector<string>> tickets) {
	vector<string> answer,temp;
	int endCnt = 0;//전체 배열 방문하면 종료 위한 변수
	sort(tickets.begin(), tickets.end());

	dfs("ICN", tickets,temp,answer,0);//출발 위치, 여행지 정보, 여행 경로 




	return answer;
}
int main(void) {
	vector<string> a;
	//a = solution({ {"ICN", "JFK"},{"HND", "IAD"},{"JFK", "HND"} });
	//a = solution({ {"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"}});
	a = solution({ {"ICN","C"},{"C","L"},{"L","D"},{"D","S"},{"S","C"} });
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

와 드디어 성공했네요 이문제는 쉬우면서도 조건을 잘 생각해줘야하는것 같아요

우선 정렬을 우선적으로 해야하는것도 포인트 입니다. 잘 생각해보시고 문제를 적용해 보세요.