프로그래머스 level 3 연습-여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

미완: 테스트 케이스는 전부 맞았지만 채점에서 1,2번 케이스가 틀려서 원인 분석중에 있습니다.

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
vector<bool> bCheck;
vector<string> stack;
vector<vector<string>> ticketsBackUp;
string lastString;
int ticketsSize;
vector<string> Dfs(vector<vector<string>> tickets,int index,int j){
    
    cout<<endl;
     for(int i=0;i<ticketsBackUp.size();i++){
        cout<<ticketsBackUp[i][0];
        cout<<",";
         cout<<ticketsBackUp[i][1];
        cout<<endl;
    }
    cout<<endl;
    
    stack.push_back(tickets[index][0]);
    ticketsBackUp.erase(ticketsBackUp.begin()+index);
    bCheck[index]=true;
     j++;
    
    if(j==ticketsSize){
        stack.push_back(tickets[index][1]);
        
        
    }
    
    
    for(int i=0;i<tickets.size();i++){
       
        if(tickets[index][1]==tickets[i][0]&& bCheck[i]==0){
             
              Dfs(tickets,i,j);
        }
        
    }
   
  
    return stack;
    
    
}


vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    int j=0;
  
     ticketsSize=tickets.size();
    for(int i=0;i<tickets.size();i++){
        bCheck.push_back(false);
        
    }
   
    
          
  //  sort(tickets.begin(),tickets.end(),greater<vector<string>>());
    
          for(int i=0;i<tickets.size();i++){
              for(int k=0;k<tickets.size();k++){
                  
                  if(tickets[i][0]==tickets[k][0]){
                      if(tickets[i][1]<tickets[k][1]){
                          string tmp;
                          tmp=tickets[i][1];
                          tickets[i][1]=tickets[k][1];
                          tickets[k][1]=tmp;
                      }
                  }
              }
          }
        ticketsBackUp=tickets;
  //  while(tickets.size()>0){
       int start=0;
       for(int i=0;i<tickets.size();i++){
            if(tickets[i][0]=="ICN"){
                start=i;
                break;
            }
       }
    
    
        answer=Dfs(tickets,start,j);
    
    for(int i=0;i<ticketsBackUp.size();i++){
        cout<<ticketsBackUp[i][0];
        cout<<",";
         cout<<ticketsBackUp[i][1];
        cout<<endl;
    }
    
   
      //}
        
    
    
    return answer;
    
    
}

정확한 이유를 알수 가 없어서 

https://programmers.co.kr/learn/questions/7894

프로그래머스

질문코너에 테이트 케이스 1,2번이 안되는 질문이 많았습니다 보니까 문제의 지문이 썩 좋지는 않았습니다. 

질문을 보면 테이스트 케이스의 무조건 정렬이 아니라 모든 도시를 방문하게 주어주는것 이것을 지켜야 하는것 같습니다. 

 

즉 모든 도시의 경로를 갈수 있을시에 정렬을 하라는 의미 인것 같습니다. 

만일 정렬을 먼저 한후에 도시 경로를 탐색 했을때 경로가 남았을 경우 그 경로로 가면 안됩니다.

 즉 미리 경로를 검색해서 최선의 경로를 만들어야 하는것 같습니다.

문제를 정확하게 표현했으면하는데 이부분은 문제를 몇번을 읽어도 이해가 쉽지 않았습니다. 

정답: 

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

using namespace std;
vector<bool>bCheck;
vector<string>stack;


bool Dfs(string str,vector<vector<string>> &tickets,int cnt){
    
    stack.push_back(str);
    
    if(cnt==tickets.size()){ //끝까지 노드 탐색했으면 true반환
       
        return true;
        
    }
    for( int i=0;i<tickets.size();i++){ //현재 자식노드 존재여부 탐색
        if(tickets[i][0]==str&&bCheck[i]==false){ //현재 노드와 일치하며 아직 진행하지 않는 노드 발견
            bCheck[i]=true; //진행 했다고 알려주는 flag 
            bool bPass=Dfs(tickets[i][1],tickets,cnt+1); //다음 자식노드로 이동 ,만약 모든 노드를 탐색을 완료 했을시 true 반환
            if(bPass==true){ // 모든 노드를 탐색을 완료 했을시 true 반환
                return true;
                }else{
            
            bCheck[i]=false; //만약 탐색이 완료되지 않는경우 현재 노드 false로 flag 변경 진행하지 않는걸로 만듬
            }
        }
    }
    stack.pop_back(); //현재 노드 stack에서 제거 
    return false; //현재노드로 진행방향이 올바르지 않았으므로 false로 반환 
    
    
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
 
    for(int i=0;i<tickets.size();i++){
        bCheck.push_back(false);
    }
    
    sort(tickets.begin(), tickets.end());

    Dfs("ICN",tickets,0);
     answer=stack;
    return answer;
}

200821- 다시 풀려니까 1번문제가 계속해서 틀림 이유를 잘모르겟음

그리고 이전에 풀었던게 훨씬 간결하게 잘풀엇음 참고하여 오답노트 만들예정

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
struct PairTicketDataStru{
    
    pair<string, string >trip;
    bool bCheck;
};

bool cmp(const PairTicketDataStru v1,const PairTicketDataStru v2){

    if(v1.trip.first==v2.trip.first){
        if(v1.trip.second<v2.trip.second){
            return true;
            }
    }
    return false;
    
}

vector<string>saveData;
bool Trip(vector<PairTicketDataStru>ticketsPairStru,int totalCount,int index,int count,vector<string>saveTmpData){
    if(totalCount==count){
       
        saveTmpData.push_back(ticketsPairStru[index].trip.first);
         saveTmpData.push_back(ticketsPairStru[index].trip.second);
        saveData=saveTmpData;
       
        return true;
    }
    
    
    for(int i=0;i<totalCount;i++){
        if(ticketsPairStru[index].bCheck==false){
            ticketsPairStru[index].bCheck=true;
           
        }
        
        if(ticketsPairStru[index].trip.second==ticketsPairStru[i].trip.first&&ticketsPairStru[i].bCheck==false){
            cout<<"i."<<i<<":";  
           cout<<"["<<ticketsPairStru[index].trip.first<<","<<ticketsPairStru[index].trip.second<<"]"<<",";
            cout<<"["<<ticketsPairStru[i].trip.first<<","<<ticketsPairStru[i].trip.second<<"]"<<",";
              ticketsPairStru[i].bCheck=true;
              
              saveTmpData.push_back(ticketsPairStru[index].trip.first);
              bool bTmpCheck=Trip(ticketsPairStru,totalCount,i,count+1,saveTmpData);
          
              if(bTmpCheck==true){
                  
                return true;
                  
              }else{
                  cout<<endl;
                 
                  saveTmpData.pop_back();
               
                  ticketsPairStru[i].bCheck=false;
                  ticketsPairStru[index].bCheck=false;
                 
              } 
            
        }
  
    }
   
    
    
               
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<PairTicketDataStru>ticketsPairStru;
  
    for(int i=0;i<tickets.size();i++){  
        PairTicketDataStru tmp;
        pair<string, string >tmpP;
        tmpP.first=tickets[i][0];
        tmpP.second=tickets[i][1];
        tmp.trip=tmpP;
        tmp.bCheck=false;
        ticketsPairStru.push_back(tmp);
    }
    
    sort(ticketsPairStru.begin(),ticketsPairStru.end(),cmp);
    int totalCount=tickets.size();
    int count=1;
    bool bCheckData=false;
    vector<string>saveTmpData;
    for(int i=0;i<ticketsPairStru.size();i++){
        if(ticketsPairStru[i].trip.first=="ICN"){
          
        
            //cout<<i<<":";
           // cout<<i<<","<<totalCount<<","<<count<<",";
            bCheckData=Trip(ticketsPairStru,totalCount,i,count,saveTmpData);
             //cout<<endl;
            if(bCheckData==true){
            
                
                i=ticketsPairStru.size()+1;
                break;
                
            }else{
              //  cout<<"!";
               // cout<<endl;
                
              // cout<<ticketsPairStru[1].bCheck;
            }
        }
        
    }
    
    //for(int i=0;i<saveData.size();i++){
  //   cout<<saveData[i]<<",";
   // }
  answer= saveData;
    return answer;
}

 

 

20201008

#include <string>
#include <vector>
#include<iostream>
#include<string.h>
#include<cstring>
#include<algorithm>

using namespace std;
struct pathDataStru{
    string arrive;
    int index;
    
    
};

bool cmp(const pathDataStru &p1,const pathDataStru &p2){
    if(p1.arrive.compare(p2.arrive)<0){
        return true;
    }else if(p1.arrive.compare(p2.arrive)==0){
        return true;
    }
     return false;
    
    
}
vector<string>arriveData;
bool func(vector<vector<string>> tickets,vector<bool>bCheck,string find,int pathCount,int count){
    if(pathCount<count){
       
        if(arriveData.size()>=pathCount){
           // cout<<arriveData.size();
             // cout<<pathCount;
            return true;
               
           }
         return false;
    }
    
    vector<pathDataStru>pathStru;
    //검증
    for(int i=0;i<tickets.size();i++){
        
        if(tickets[i][0]==find&&bCheck[i]==false){
        pathDataStru tmpStru;
        tmpStru.arrive=tickets[i][1];
        tmpStru.index=i;
        pathStru.push_back(tmpStru);
        }
    }
    //cout<<find<<",";
    if(pathStru.size()>0){
        if(pathStru.size()>=2){
           
            sort(pathStru.begin(),pathStru.end(),cmp);
            //cout<<pathStru[0].arrive;
            for(int i=0;i<pathStru.size();i++){
               find=pathStru[i].arrive;
              //   cout<<"+"<<find<<",";
                
                 
                
                arriveData.push_back(pathStru[i].arrive);
               
                
                bCheck[pathStru[i].index]=true; //input시 true
                 
               bool bFuncCheck= func(tickets,bCheck,find,tickets.size(),count+1);
               //   cout<<bFuncCheck;
                if(bFuncCheck){
                    return true;
                }else if(!bFuncCheck){
                    
                 
           //       cout<<"!";
             //      cout<<"-"<<arriveData[arriveData.size()-1]<<",";
                   
                    
                    
                
                 bCheck[pathStru[i].index]=false; //돌아올때 false 경로를 전부 지나는 경로가 아닐경우 
                 arriveData.pop_back();
                    
                      
                  
                
                }
                
            }
           // func(tickets,bCheck,find,tickets.size(),count);
            
            
        }else if(pathStru.size()<2){
             find=pathStru[0].arrive;
             bCheck[pathStru[0].index]=true;
            
                
                arriveData.push_back(find);
            
           
            bool bFuncCheck= func(tickets,bCheck,find,tickets.size(),count+1);
            if(bFuncCheck){
                return true;
            }
            else if(!bFuncCheck){
                 bCheck[pathStru[0].index]=false; //돌아올때 false 경로를 전부 지나는 경로가 아닐경우 
                 arriveData.pop_back();
                    
                return false;
            }
            
        }
        
    }
    
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool>bCheck;
   
    for(int i=0;i<tickets.size();i++)
        bCheck.push_back(false);
    
    
       arriveData.push_back("ICN");
    
    
    func(tickets,bCheck,"ICN",tickets.size(),1);
   
    answer=arriveData;
    
    
    return answer;
}

 

가장 기본적인 경로를 따라가는걸 구현할때 

도착지점이 같은 경로들이 존재한다. 

이럴경우 같은 경로중 도착에 알파뱃 순으로 지정한다. 

이때 sort 정렬을 이용해준다 .

만약 

도착 지점에 더이상 도착 하지못하는 경우가 생기면 

 

그 이전 경로로 돌아가서 다시 길을 찾도록 한다 

여기서 조건은 무조건 경로를 전부 돌아야한다 .

아마 대부분의 사람들이 이것 때문에 시간 낭비를 하는듯 하다.

문제가 별로 안좋다 . 조건을 확실히 적어줘야는데 애매하게 전부 다 갈수있는것처럼 표기되어있다 조건을 잘 설명해준 문제는 아니다.

 

그 조건을 이용하여 만약에 도착했을경우에 true로 반환 도착하지 못했을경우엔 false로 반환후에 

false인경우에는 이전 도착 경로와 경로를 지낫다는 사실을 없애줘야한다. 

 

그러면 더이상 알파뱃 순으로 아닌 이후 알파뱃순으로 경로를 찾는다.