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

https://programmers.co.kr/learn/courses/30/lessons/43164?language=cpp 

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

 

- DFS/BFS 문제이다. 

 

- 가장 먼저, dfs를 어떻게 구현 할 지를 생각해야 한다. dfs함수의 매개변수에는 tickets배열, 현재 머무는 공항의 이름, 현재까지의 모든 경로를 문자열로 기록 해 놓은 path, 티켓을 얼마나 사용했는 지를 나타내는 count변수를 사용한다. dfs를 구현하는 경우, 최대 약 10000번 dfs 호출 * 내부의 10000번의 for문을 거치므로 1억 이하의 연산이 나와서, 시간초과를 걱정하지 않아도 된다. 

 

- dfs를 호출한다. 가장 먼저, return 조건문을 작성한다. count가 ticket의 size와 같을 때, 즉 모든 ticket을 사용한 경우가 종결 조건이다. 이 경우, ans_string과 새로운 path를 비교하여 사전순으로 더 앞서는 string을 답으로 정한다. 

 

- 다음으로, 모든 티켓을 순환하면서 dfs를 추가로 호출한다. 여기서 선택될 티켓은 현재 머무는 공항이 티켓의 첫 번째 값과 동일한 경우이다. 해당 티켓을 선택했다면, visited를 true로 바꾸어 주고, dfs를 추가로 호출한다. 이 때, dfs호출을 마치고 visited를 false로 돌려놓는 과정을 잊지 말자. 

 

- dfs 호출이 끝났다면, 마지막으로 answer_path에서 차례대로 문자열을 추출하여 answer에 push한다. 만약 answer_path를 문자열이 아닌 벡터 형식으로 사용했다면, answer_path와 new path간에 요소들을 하나씩 꺼내서 사전순으로 일일이 비교를 해야하기 때문에, 코드가 조금 더 복잡해졌을 것이다. 

#include <string>
#include <vector>
using namespace std;
int visited[1000000];
string answer_path = "a";

void dfs(vector<vector<string>> &tickets, string cur, string path, int count) {
    if (count == tickets.size()) {
        string p = path;
        if (path < answer_path) {
            answer_path = path;
        }
        return;
    }

    for (int i = 0; i < tickets.size(); i++) {
        if (cur == tickets[i][0] && !visited[i]) {
            visited[i] = 1;
            dfs(tickets, tickets[i][1], path + tickets[i][1], count+1);
            visited[i] = 0;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    dfs(tickets, "ICN", "ICN", 0);
    for (int i = 0; i < answer_path.size(); i+=3) {
        answer.push_back(answer_path.substr(i, 3));
    }
    return answer;
}