(DFS/BFS)여행경로

처음 풀이

기저사례 : 단순히 티켓의 개수에 집중해서 규칙으로 끼워맞추려고 함
1.ICN부터 출발해서 (도착,다음 출발) -(도착,다음 출발)-마지막 도착 이런 식으로 묶으면 결국 티켓의 사이즈와 동일한데 생각하지 못함
2.재귀함수를 종료하기 위해서는 재귀함수 파라미터에 인덱스를 증가시키면서 탈출조건과 맞도록해야하는데 1번을 생각하지 못해서 마지막에 출력하는 경로의 사이즈와 티켓의 개수로 처리

로직

for(int i=0;i<tickets.size();i++){
         string to=tickets[i][1];
  if(tickets[i][0]==start && !visited[i]){
              answer.push_back(to);
              visited[i]=1;
              sort(tickets.begin(), tickets.end());
              recur(tickets[i][1],tickets,cnt+1);
              visited[i] = 0;
              answer.pop_back();

          }
    }

위의 코드로 디버깅을 해보면 문제에서 주어진 2번째 테스트케이스를 돌려보면 정답출력과 동일하게 나오지만 방문여부와 pop_back()에 대한 조건을 따로 처리해 주지않아서 알파벳순이아닌 정답으로 출력이 나옴
-> 기저사례를 만족했을 때 다른 경우를 찾지 않도록 혹은 기저사례를 만족하지 않는 경우가 있을 때만 방문처리를 취소하고 pop_back()하는 조건을 처리 했을 때 모든 조건을 만족하게 된다

다른 사람들의 코드를 봤을 때 이러한 경우를 처리할 때는 bool형때의 flag를 선언하여 조건만족시 true/false만 설정을 해서 코드를 짜면 더 보기 편하다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
int cnt;
vector<string> answer;
vector<string> path;
// bool flag=false;
int visited[10000004];



void recur(string start, vector<vector<string>> tickets,int cnt){
    if(cnt==tickets.size()){
        path=answer; // flag=ture;
        return;
    }


    for(int i=0;i<tickets.size();i++){
         string to=tickets[i][1];
        if(tickets[i][0]==start && !visited[i]){

            answer.push_back(to);
            visited[i]=1;
            sort(tickets.begin(), tickets.end());
            recur(tickets[i][1],tickets,cnt+1);
            if (path.size()==0) { // if(!flag)
                visited[i] = 0;
                answer.pop_back();
            }


        }

    }

}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());

    string start="ICN";
    answer.push_back(start);
    recur(start,tickets,cnt);
    return path;
}