✅ LV. 3
🔖 DFS
push
하는 함수 선언answer
return
visit
처리answer
벡터에 추가하고 출발지로 갱신pop
해서 초기화테케 2개 실패ㅠ
중복되는 티켓에 대한 처리 안함?
DFS
안 쓰다보니 while
문과 불필요한 함수 정의 남발tickets
벡터를 정렬해주고 시작하는 편이 효율적visit
처리해야하는데 인덱스를 그때마다 찾아줘야 하는 것이 비효율적vector<bool> visit
: 티켓 방문여부 저장bool DFS(string cur, vector<vector<string>> ticket, vector<string> &answer, vector<bool> &visit, int cnt)
cur
: 현재 출발지cnt
: 사용한 티켓 count
DFS
들어가기 전, tickets
정렬cnt == ticket.size()
) true
return
ticket
을 for 문을 돌면서 현재 출발지를 출발지로 가지면서 아직 방문하지 않았을 경우visit
표시++cnt
해서 해당 경로의 도착지를 출발지(cur
) 에 넣어 DFS
수행DFS
return
값이 false
이면 그 경로로 DFS 탐색했을 때, 모든 티켓을 탐색하지 못한다는 뜻이기 때문에 visit
표시 해제return
되지 못하면 cur
을 출발지로 가지는 경로로는 티켓을 소진하지 못한다는 의미이기 때문에 DFS
처음에 answer
에 push
했던 cur
을 pop
해주고 false
return
❗️ visit
은 중복 티켓 사용을 막기 위한 목적, cnt
는 티켓을 전부 소진했는지 확인해서 탐색을 종료하기 위한 목적으로 사용
DFS
를 사용해 같은 도착지를 가질 때, 우선순위 경로로 탐색을 실패했을 경우, 차선책 경로로 탐색을 시도할 수 있도록 구현이 필요했다.DFS
나 BFS
로 구현할 수 있도록 노력하자..괜히 반복문 남발하지 않고,, BFS
가 아니라면 큐 사용은 지양하는 것으로,,#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool DFS(string cur, vector<vector<string>> ticket, vector<string> &answer, vector<bool> &visit, int cnt) {
answer.push_back(cur);
if (cnt == ticket.size()) return true;
for(int i = 0 ; i < ticket.size(); i++) {
if (ticket[i][0] == cur && visit[i] == false) {
visit[i] = true;
bool T = DFS(ticket[i][1], ticket, answer, visit, ++cnt);
if (T == true) return true;
visit[i] = false;
}
}
answer.pop_back();
return false;
}
vector<string> solution(vector<vector<string>> tickets) {
vector<string> answer;
vector<bool> visit(tickets.size(), false);
sort(tickets.begin(), tickets.end());
DFS("ICN", tickets, answer, visit, 0);
return answer;
}