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

programmers.co.kr/learn/courses/30/lessons/43164#

코딩테스트 연습 - 여행경로

 

아악 내 반나절을 앗아간 문제..............너어어어어는 진짜.... 반나절을 앗아갔으므로 풀이를 해야 겠다.

나는 테스트 케이스 2번이 계속 통과가 안됐었는데, 찾아보니 반례가 아래 예제였다,

 

ICN -> A,

ICN -> B,

B -> ICN

 

알파벳 순으로 가야 하니까 이걸 정렬해서 ICN 부터 들어가게 되면 ICN -> A로 들리게 되고, 그렇게 되면 A가 더 이상 갈 수 있는 곳이 없으므로 다른 ICN을 시작점으로 해야 한다.

 

틀린 이유 1 :

알파벳 순 정렬 후에 맨 앞에 있는 ICN과 그 도착점이 항상 처음으로 거칠 두 장소라고 볼 수 없는데 난 미리 맨 첫 ICN 를 발견하자마자 ICN과 그 도착지를 모두 answer에 넣어놓고 시작했었다. 위의 반례의 경우에는 이렇게 하면 오답이다. 따라서 ICN도 탐색해서 넣어야 한다. 이 ICN과 그 도착점을 첫 장소로 했을 때 모든 티켓을 다 사용할 수 있는지 말이다.

 

틀린 이유 2 :

최초로 tmp가 다 채워졌으면 그게 최종 답이다. 갈 수 있는 경로가 여러 개일 때 알파벳이 앞서는 걸 답으로 했기 때문에 정렬한 상태에서 첫 answer를 찾았으면 더 이상 찾으면 안된다. 가능한 경로가 2개일 경우 첫 번째가 답인데 여기서 dfs를 끝내지 않으면 두 번째 가능한 경로가 최종 답이 되어 리턴되니까 조심해야 한다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool dfs(string start, vector<vector<string>> &tickets, vector<string> &answer, 
                   vector<string> &tmp, vector<bool> &visit){
    if(tmp.size() == tickets.size() +1 ){
        answer = tmp;
        return true;
    }
    
    for(int i = 0; i<tickets.size(); i++){
        if(!visit[i] && tickets[i][0] == start){
            visit[i] = true;
            tmp.push_back(tickets[i][1]); 
            bool success = dfs(tickets[i][1], tickets, answer, tmp, visit);
            if(success){
                return true;
            }
            visit[i] = false;
            tmp.pop_back();
        }
        
    }
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<string> tmp;
    vector<bool> visit(tickets.size());
    
    sort(tickets.begin(), tickets.end());
    tmp.push_back("ICN");
    dfs("ICN", tickets, answer, tmp, visit);
    
    return answer;
}

 

그래서 answer에는 처음에 ICN만 넣어두고 그 도착점은 탐색한다. 몇 번째 ICN이 답인지 모르니까.

 

틀린이유 1 을 개선하기 위해 첫 ICN을 start로 해서 이걸 출발점으로 갖는 ticket을 dfs의 for문으로 탐색한다.

ticket을 모두 쓰지 못하는 ICN 출발 티켓이라면 이건 버리고,,, 다른 ICN  출발 티켓을 찾는 것이다.

 

틀린 이유 2 를 개선하기 위해 success 를 체크한다. 가능한 경로가 두 개일 경우 첫 경로만 답인데 여기서 dfs를 끝내지 않으면 가능하지만 오답인 경로가 최종 답으로 결정되어 리턴된다. 이걸 막기 위해 success를 둬서 제대로 된 첫 answer를 찾았으면 더 이상 for문을 돌지 말고 바로 dfs 자체를 리턴하게 하자.