BFS로 삽질 과정
1. tickets를 알파벳 순으로 정렬
2. 출발지가 ICN인 경우, bfs 돌려서 모든 항공권을 사용한 경우, true 리턴 or false 리턴
3. false인 경우, 다음 ICN 항공권 사용해서 다시 bfs 돌림
4. 테케 1번이 절대 통과되지 않음
❓ 반례
`입력`
[["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
`정답`
["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]
→ WHY ? 가는 도중에 알파벳 순으로 가면 모든 항공권을 쓸 수 없는 길이 끊긴 예외 경우 발생하기 때문 ..
→ 처리할 예외의 경우가 너무 많다 ... 다른 방법 없을까 ?
✅ DFS 재귀 사용하여 모든 경우의 수 체크하면 가능하겠다 !
DFS
#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> ticket;
vector<string> answer;
bool check[10001];
bool isAnswer;
void dfs(string start, int ticketCnt){
answer.push_back(start);
if (ticketCnt == ticket.size()) {
isAnswer = true;
}
for (int i = 0; i < ticket.size(); i++) {
if (check[i]) continue;
if (ticket[i][0] == start) {
check[i] = true;
dfs(ticket[i][1], ticketCnt+1);
if (!isAnswer) {
answer.pop_back();
check[i] = false;
}
}
}
}
vector<string> solution(vector<vector<string>> tickets) {
sort(tickets.begin(), tickets.end());
ticket = tickets;
dfs("ICN", 0);
return answer;
}