[C++/프로그래머스] 여행경로

✅ LV. 3
🔖 DFS

✏️ 1차 솔루션

• 현재 출발지에 대한 도착지 후보 벡터에 push 하는 함수 선언
• 이미 사용한 티켓은 벡터로 관리

1. 큐가 비어있으면 더 이상 도착할 곳이 없다고 판단해 answer return
2. 도착지 후보를 알파벳 순서로 정렬
3. 도착지 후보 중 첫번째를 도착지로 가지는 인덱스 찾아서 visit 처리
4. 도착지를 answer 벡터에 추가하고 출발지로 갱신
5. 나머지 채택되지 못한 도착지 후보들 다음 분기를 위해 pop 해서 초기화

🚨 1차 trouble

테케 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 정렬

1. 모든 티켓 탐색시(cnt == ticket.size()) true return
2. ticket 을 for 문을 돌면서 현재 출발지를 출발지로 가지면서 아직 방문하지 않았을 경우
   1) 해당 경로 visit 표시
   2) ++cnt 해서 해당 경로의 도착지를 출발지(cur) 에 넣어 DFS 수행
   ➡️ DFS return 값이 false 이면 그 경로로 DFS 탐색했을 때, 모든 티켓을 탐색하지 못한다는 뜻이기 때문에 visit 표시 해제
3. 2번 과정에서 return 되지 못하면 cur 을 출발지로 가지는 경로로는 티켓을 소진하지 못한다는 의미이기 때문에 DFS 처음에 answer 에 push 했던 cur 을 pop 해주고 false return

❗️ visit 은 중복 티켓 사용을 막기 위한 목적, cnt 는 티켓을 전부 소진했는지 확인해서 탐색을 종료하기 위한 목적으로 사용

📌 self feedback

• 조건이 불친절하기는 했지만 알파벳 순으로 탐색하더라도 모든 티켓을 소진해 탐색을 할 수도 있고 못할 수도 있는 상황을 고려해 예외 처리를 했어야 했다.
• 따라서 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;
}