[프로그래머스 / C++] 여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164
문제풀이
-
처음엔 인접행렬을 어떻게 만들어주지..? 하다가 꼬였다.
dfs에시작점 인자(string)
를 보내고, dfs내에서 tickets 배열을 돌면서 첫번째 열 요소가 현재 시작점과 같으면 두번재 열 요소인 도착점으로 경로를 보내면 된다. -
모든 티켓을 사용해야하므로, dfs level이 tickets.size()와 같아질 때 종료한다.
-
정렬을 하고 나서 경로를 찾는데, 한 번 경로를 찾았으면 더 이상 찾을 거 없이 종료해야 한다는 것! bool dfs를 이용해 구현하였다.
-
answer는 vector형라서 도착점을 뒤에 push_back하면서 경로를 만들어주었다. 따라서 백트래킹 했을 경우
pop_back
을 해주어야함!
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[100001];
vector <string> answer;
bool dfs(int l,string start,vector<vector<string>> tickets){
//모든 경로를 탐색했을 경우
if(l==tickets.size()){
return true;
}
for(int i=0;i<tickets.size();i++){
if(start==tickets[i][0]&&!visited[i]){ //start가 갈 수 있는 곳 중 방문하지 않은 경로
visited[i]=1;
answer.push_back(tickets[i][1]);
bool check=dfs(l+1,tickets[i][1], tickets);
if(check) return true; // 하나라도 탐색을 더 이상 탐색 안 함 return
visited[i]=0;
answer.pop_back();
}
}
return false;
}
vector<string> solution(vector<vector<string>> tickets) {
sort(tickets.begin(),tickets.end()); // 알파벳 순서가 앞서는 경로로
//인천부터 시작
answer.push_back("ICN");
dfs(0,"ICN", tickets);
return answer;
}
Author And Source
이 문제에 관하여([프로그래머스 / C++] 여행경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/프로그래머스-C-여행경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)