[프로그래머스] level 3 - 여행경로, C++

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

프로그래머스

본 문제는 DFS 문제로 주어진 모든 항공권을 이용하여 여행하는 방법을 찾는 문제다. 이때, 경로가 여러개인 경우 알파벳 순으로 앞선 경우를 return 한다.

다른 어려운 DFS/BFS 문제들은 연산량이 많아 메모리 초과가 되어 다른 방식으로 DFS/BFS 연산을 해야 하는데 이 문제는 딱 한가지 경우를 생각 못하면 풀기 힘든 문제다.

바로 [["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]] 다.

실제 시험에서 출제되었을 경우 난 틀렸을 문제다. 문제 조건중 알파벳이 앞선 경우를 return 해야하기 때문에 sort를 해야한다. 그렇게 되면 [["ICN", "BOO"], ["ICN", "COO"], ["BOO", "DOO"], ["COO", "ICN"]] 와 같이 정렬되어 탐색을 ICN->BOO->DOO만 할 수 있게 되어 모든 항공권을 이용하는 문제의 조건에 틀리게 된다. 그렇기 때문에 방문할 여행지가 없을 경우 진짜로 모든 항공권을 다 사용하여 방문할 여행지가 없는 경우인지 확인을 해야한다.

input : [["ICN","COO"],["ICN","BOO"],["COO","ICN"],["BOO","DOO"]]

output : ["ICN","COO","ICN","BOO","DOO"]

wrong : ["ICN","BOO","DOO"]

<틀린 소스코드>

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
vector<string> answer;
void dfs(string go, vector<vector<string>>& tickets, vector<bool>& chk, int cnt) {
    if(cnt == tickets.size()) {
        answer.push_back(go);
        return;
    }
    for(int i = 0; i < tickets.size(); i++) {
        if(tickets[i][0] == go && !chk[i]) {
           chk[i] = true;
            answer.push_back(go);
            dfs(tickets[i][1], tickets, chk, cnt+1);
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    
    vector<bool> chk(tickets.size(), false);
    sort(tickets.begin(),tickets.end());
    dfs("ICN", tickets, chk, 0);
    return answer;
}

 

<맞은 소스코드>

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
vector<string> answer;
bool dfs(string go, vector<vector<string>>& tickets, vector<bool>& chk, int cnt) {
    answer.push_back(go);
    if(cnt == tickets.size()) return true;
    for(int i = 0; i < tickets.size(); i++) {
        if(tickets[i][0] == here && !chk[i]) {
           chk[i] = true;
            bool is_true = dfs(tickets[i][1], tickets, chk, cnt+1);
            if (is_true) return true;
           chk[i] = false;
        }
    }
    answer.pop_back();
    return false;
}
 
vector<string> solution(vector<vector<string>> tickets) {
 
    vector<bool> chk(tickets.size(), false);
    sort(tickets.begin(),tickets.end());
    dfs("ICN", tickets, chk, 0);
    return answer;
}