알고리즘(C++) / 프로그래머스 level 3 : 여행경로

level 3 : 여행경로

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

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

 

코드

//프로그래머스 여행경로
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<string>> tickets_copy;
bool visited[10001] = { false, };
vector<string> answer;
bool check = false;

void DFS(string country, int cnt) {
    answer.push_back(country);
    if (cnt == tickets_copy.size()) {
        check = true;
        return;
    }

    for (int i = 0; i < tickets_copy.size(); i++) {
        if (tickets_copy[i][0] == country && visited[i] == false) {
            visited[i] = true;
            DFS(tickets_copy[i][1], cnt + 1);
            if (check == true)
                return;
            visited[i] = false;
        }
    }
    answer.pop_back();
    return;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end()); //정렬
    tickets_copy = tickets; //전역변수

    DFS("ICN", 0); //ICN 시작

    return answer;
}

int main() {
    vector<vector<string>> tickets = { {"ICN", "A"},{"ICN", "B"},{"B", "ICN"} };

    solution(tickets);

    return 0;
}

 

설명

• DFS를 이용하여 문제를 풀 수 있다.
• 오름차순으로 정렬된 tickets을 전역변수로 바꿔 선언해주고 방문했는지 확인하는 visited도 전역변수로 선언해주었다.
• 항상 "ICN" 공항에서 출발한다고 하였으므로 ICN에서 탐색을 시작한다. 
• DFS는 입력받은 country에서 시작하는 ticket을 찾고 이동한다. visited를 true로 입력해준다. 
• 모든 항공권을 사용하였다면 check를 true로 저장하여 탐색을 종료한다. 
• 알파벳 오름차순으로 정렬하였기 때문에 처음으로 모든 항공권을 사용했을 때가 알파벳 순서가 앞서는 경로로 return 할 수 있다.
• 변수 cnt로 ICN에서 부터 거리를 나타낼 수 있다. 

 

고찰

어려워보이지 않았지만 쉽게 풀지 못하였다...

여러 경로일 때를 고려하여 다시 풀었다.