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

 

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

프로그래머스

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

using namespace std;

vector<string> path;
vector<string> answer;
vector<int> visited;

void dfs(vector<vector<string>> tickets, string loc, int cnt) {
    if (cnt == tickets.size()) {
        answer = path;
        return;
    }

    for(int i=0; i<tickets.size(); i++) {
    	if (visited[i]) continue;
        if (tickets[i][0].compare(loc)==0) {
            // idx와 cnt 구분
            visited[i] = 1;
            cnt++;
            path.push_back(tickets[i][1]);
            dfs(tickets, tickets[i][1], cnt); // 반환값
            visited[i] = 0;
            path.pop_back();
            cnt--;
        }
    }
}

bool cmp(vector<string> a, vector<string> b) {
    if (a[0] == b[0]) return a[1] > b[1];
    return a[0] < b[0];
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end(), cmp);
    visited.assign(tickets.size(), 0);
    
    path.push_back("ICN");
    dfs(tickets, "ICN", 0);
    //answer.clear(); // empty() X

    return answer;
}

---

※ TC 1개 실패 코드

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

using namespace std;

vector<string> answer;

bool dfs(vector<vector<string>> tickets, string loc, int visited[], int idx, int cnt) {
    // idx와 cnt 구분
    visited[idx] = 1;
    cnt++;
    answer.push_back(loc);
    
    if (cnt == tickets.size()) return true;

    for(int i=0; i<tickets.size(); i++) {
        if (visited[i] == 0 && tickets[i][0].compare(loc)==0) {
            return dfs(tickets, tickets[i][1], visited, i, cnt); // 반환값
        }
    }
    return false;
}

bool cmp(vector<string> a, vector<string> b) {
    if (a[0].compare(b[0])==0) {
        if(a[1].compare(b[1])>0) return false;
        else return true;
    }
    else {
        if(a[0].compare(b[0])>0) return false;
        else return true;
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end(), cmp);
    
    for(int i=0; i<tickets.size(); i++) {
        if (tickets[i][0].compare("ICN")==0) {
            answer.push_back("ICN");
            
            // for문 내에서 초기화
            int visited[tickets.size()]; // erase 대신 visited 사용
            for(int i=0; i<tickets.size(); i++) visited[i] = 0;
            
            if (dfs(tickets, tickets[i][1], visited, i, 0) == true) break;
            else answer.clear(); // empty() X
        }
    }
    return answer;
}