문제 이해 단계
알파벳 대문자 3글자로 이루어진 공항(정점)이 존재한다.
그리고 입력으로 티켓(간선) [a, b] 형태로 a->b 로이 단방향 정보로 주어진다.
이때, 모든 항공권을 사용한다는 말은 모든 간선을 사용한다는 말이다.
모든 도시를 방문할 수 없는 경우는 주어지지 않는다는 말은 결국엔 모든 정점을 방문한다는 소리이다.
이때 방문했던 공항 순서대로 출력하도록 하는 게 해당 문제이다.
여기서 한 공항에서 티켓이 여러 개 있다면 사전순(오름차순)으로 더 빠른 것이 우선시된다.
문제 접근 단계
해당 문제는 위에서 말했듯이 공항은 정점이고, 티켓은 두 정점을 잇는 단방향 정보인 간선이다.
그렇기 때문에 해당 문제는 그래프 탐색 문제일 가능성이 높다.
그래서 BFS 또는 DFS로 접근해야 할 것 같은데,
문제에서 요구하는 답은 ICN 공항에서 출발하여 경로를 거친 순서대로 출력하는 것이다.
따라서, 오직 한 가지의 경로에 대해서만 중점을 맞추는 DFS로 접근하는 것이 맞는 것 같다.
여기서는 노드들과 정점들이 모두 정수형이 아닌 문자열로 주어졌기 때문에
인덱스를 일반적인 받는 것을 불가능하다.
그래서 자료형 중에 map을 사용하여
<string, vector <string>>쌍으로 정의할 것이다.
map은 key-value 쌍으로 key값을 통해 해당 key와 연결된 value를 찾을 수 있다.
그래서 출발하는 공항 이름을 key로 도착하는 공항 이름을 value로 받는다.
근데 벡터로 받아준 이유는 티켓이 여러 장이라,
한 공항에서 다른 공항으로 가는 티켓이 존재할 수 있기 때문이다.
예를 들어 "ICN" 공항에서
"ABC"을 가는 티켓과 "ICN"공항에서
"DCF" 공항을 가는 티켓이 존재하는 것처럼 말이다.
다음으로 생각해야 하는 것은 해당 경로가 올바른 경로인가를 판별하는 것이다.
이게 무슨 말이냐면,
그래프를 탐색하는데 해당 경로로 이동했더니 더 이상 이동할 수는 없는데,
티켓을 다 사용하지 않은 상태일 수도 있다는 경우도 있다는 것이다.
한 예시에서 어쩌다 보니 해당 경로로 이동했다고 생각해 보자.
DFS로 그래프를 탐색하다 보면 필연적으로 이런 테스트케이스가 발생할 수 있다.
이런 경우를 어떻게 식별하고 또 어떤 식으로 처리해 줘야 할까?
나 같은 경우에는 최종적으로 나오는 경로의 개수를 보고 판단하였다.
만약 티켓의 개수가 5개였다면 경로의 요소 개수도 5개여야 한다.
왜냐하면 티켓을 다 사용해야 하니까.
즉 DFS가 끝났을 때의 경로의 개수를 판단 기준으로 세워 식별하였다.
방문 처리 같은 경우에는 한번 사용했던 경로는 없애는 방식을 사용했다.
한 경로에서의 DFS의 진행할 때 사용했던 경로는 지워버린다.
그리고 그 함수의 사용이 끝나면 경로를 다시 생성하여 다른 경로로의 DFS도 사용 가능하게 한다.
이건 말로 하면 힘드니까 밑에 구현에서 제대로 설명하겠다.
문제 구현 단계
map<string,vector<string> > paths; // 티켓의 경로를 담은 맵(출발지 - 도착지)
vector<string> dfs(string from,vector<string> s, int remain,int max){
//from = 출발지, s = 경로를 담아 넘기는 배열, remain = 남은 티켓 개수, max = 전체 티켓 개수
s.push_back(from);
if(remain <= 0) return s; // 티켓을 다 사용했으면 종료
vector<string> answer;
int cnt = 0; // 인덱스 알아내기 위한 변수
// 해당 출발지에서의 남은 경로가 없을때까지 반복
while(!paths[from].empty() && cnt < paths[from].size()){
string to = paths[from][cnt];
paths[from].erase(paths[from].begin()+cnt); // 경로 지움
answer = dfs(to,answer,remain-1,max);
if(answer.size() >= max) break; // dfs의 결과(최종 경로)가 티켓 개수면 DFS 종료
paths[from].insert(paths[from].begin() + cnt,to); // 해당 경로 다시 생성
cnt++;
}
return answer;
}그래프를 탐색하는 DFS 함수이다.
전역변수로 받은 paths에서 공항 이름을 통해 도착지를 검색하여
이를 다시 출발지로 설정하는 방식으로 진행한다.
매개변수에서 vector <string> s를 계속해서 전달하는데,
재귀함수에서 계속해서 출발지를 추가해 주는 것을 볼 수 있다.
재귀함수를 계속 진행하다 보면 마지막으로 호출되는 재귀함수에서의 s에는
지금까지 지나왔던 모든 출발지의 정보가 다 담겨 있을 것이다.
아까 말했던 방문을 확인하는 방법이 paths [from]. erase()이다.
이거는 vector에 특정 자리의 요소를 지우는 것인데,
이것으로 경로를 지워 이미 지나갔던 곳은 더 이상 방문을 못하게 한다.
그리고 반환받은 vector <string>을 확인하여
해당 요소의 개수가 티켓의 개수랑 같은지 체크한다.
같다면 더 이상 탐색할 필요가 없다.
왜냐하면 우리가 찾는 것은 사전순으로 빠른 경로를 찾는 것인데,
아래에서 이미 정렬해 놨기 때문에 먼저 호출되는 게 사전순으로 더 빠른 도착지이다.
(정렬은 아래에서 서술할 것임)
만약 아니라면, 그 경로는 틀린 것이기 때문에
재탐색을 위해 방문했던 정보를 없애기 위해 해당 경로를 다시 추가한다.
이러한 과정을 방문하여 답을 구할 수 있다.
아래는 전체 과정이다.
아래에서 중요하게 봐야 할 점은 paths에 tickets를 담아줄 때 정렬을 해준다는 것이다.
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
map<string,vector<string> > paths; // 티켓의 경로를 담은 맵(출발지 - 도착지)
vector<string> dfs(string from,vector<string> s, int remain,int max){
//from = 출발지, s = 경로를 담아 넘기는 배열, remain = 남은 티켓 개수, max = 전체 티켓 개수
s.push_back(from);
if(remain <= 0) return s; // 티켓을 다 사용했으면 종료
vector<string> answer;
int cnt = 0; // 인덱스 알아내기 위한 변수
// 해당 출발지에서의 남은 경로가 없을때까지 반복
while(!paths[from].empty() && cnt < paths[from].size()){
string to = paths[from][cnt];
paths[from].erase(paths[from].begin()+cnt); // 경로 지움
answer = dfs(to,answer,remain-1,max);
if(answer.size() >= max) break; // dfs의 결과(최종 경로)가 티켓 개수면 DFS 종료
paths[from].insert(paths[from].begin() + cnt,to); // 해당 경로 다시 생성
cnt++;
}
return answer;
}
vector<string> solution(vector<vector<string> > tickets) {
vector<string> answer;
for(int i = 0; i < tickets.size(); i++){
string from = tickets[i][0];
string to = tickets[i][1];
vector<string> str;
paths.insert(make_pair(from,str));
paths[from].push_back(to);
// 도착지 사전순 정렬
sort(paths[from].begin(),paths[from].end());
}
answer = dfs("ICN",answer,tickets.size(),tickets.size());
return answer;
}
시행착오
처음에는 set으로 구현했는데,
문제 조건에서 같은 출발지에서 같은 도착지로 가는 걸 중복할 수 없다는 말이 없었다.
그래서 set이 안 되는 것도 모르고 이걸로 했다가 틀리고 메모리 초과 나고 난리 났다.
게다가 set을 쓰다 보니 iterator를 자연스럽게 접하게 됐는데,
이걸 모르니까 iterator부터 공부했다.
iterator는 진짜 복잡한 것 같다. 그래도 대충은 알 것 같다.
해당 문제 로직은 머릿속으로 알겠는데 또 구현이 문제다.
난 항상 구현이 문제인 것 같다.