https://programmers.co.kr/learn/courses/30/lessons/43164
코딩테스트 연습 - 여행경로
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
programmers.co.kr
여행 티켓 이름을 먼저 정렬하고 난 뒤 여행 티켓을 통해 경로를 탐색하면 처음으로 나온 경로가 알파벳 순으로 가장 빠른 여행지의 경로가 된다는 것을 블로그에서 보고 그 성질을 이용해 풀었다.
소스코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> airport;
bool finish = false;
void dfs(vector<vector<string>> tickets, vector<int> &ch) {
//모든 공항을 경유한 경우 쭉 리턴
if(airport.size() == tickets.size()+1) {
finish = true;
return;
}
for(int i = 0; i< tickets.size() ; i++) {
//이미 사용한 티켓이거나 출발지가 다른 경우 스킵
if(ch[i] == 1) continue;
if(airport.back() != tickets[i][0]) continue;
ch[i] = 1;
airport.push_back(tickets[i][1]);
dfs(tickets, ch);
//이전 분기에서 이미 정답을 찾은 경우 계속 리턴
if(finish == true) return;
//아닌 경우 방문 해제
ch[i] = 0;
airport.pop_back();
}
}
vector<string> solution(vector<vector<string>> tickets) {
vector<string> answer;
//방문 체크 배열 생성
vector<int> ch(tickets.size(), 0);
//알파벳 순으로 앞에 오는 경로가 먼저 나오게 하기 위해 정렬
sort(tickets.begin(), tickets.end());
airport.push_back("ICN");
//dfs 수행
dfs(tickets, ch);
answer = airport;
return answer;
}
'CodingTest Practice > Programmers' 카테고리의 다른 글
프로그래머스 : 가장 먼 노드 (C++, Lv.3, 그래프) (0) | 2022.06.03 |
---|---|
프로그래머스 : 프린터 (C++, Lv.2, 큐) (0) | 2022.05.31 |
프로그래머스 : 단어변환(C++, Lv.3, BFS) (0) | 2022.05.27 |
프로그래머스 : 카펫 (C++, Lv.2, 완전탐색) (0) | 2022.05.25 |
프로그래머스 : 체육복 (C++, Lv.1, 탐욕법) (0) | 2022.05.22 |