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

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

Solution

#include <string>
#include <vector>
#include <algorithm>
#define MAX 10001

using namespace std;

bool visited[MAX];

bool DFS(string current, vector<vector<string>> &tickets, vector<string> &answer, int ticketIndex){
    answer.push_back(current);
    if(ticketIndex == tickets.size()) return true;
    for(int i = 0; i < tickets.size(); i++){
        if(tickets[i][0] == current && !visited[i]){
            visited[i] = true;
            if(DFS(tickets[i][1], tickets, answer, ticketIndex+1)){
                return true;
            }
            visited[i] = false;
        }
    }
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end());
    DFS("ICN", tickets, answer, 0);
    return answer;
}

우선 정렬을 해 준다. 어떻게든 알파벳 순으로 빠른 데이터 위주로 탐색을 진행해야 하기 때문이다.

bool visited[MAX];

bool DFS(string current, vector<vector<string>> &tickets, vector<string> &answer, int ticketIndex){
    answer.push_back(current);
    if(ticketIndex == tickets.size()) return true;
    for(int i = 0; i < tickets.size(); i++){
        if(tickets[i][0] == current && !visited[i]){
            visited[i] = true;
            if(DFS(tickets[i][1], tickets, answer, ticketIndex+1)){
                return true;
            }
            visited[i] = false;
        }
    }
    answer.pop_back();
    return false;
}

생각을 깊게 하지 않는다면 visited 배열에 무엇을 넣어야 할 지 고민이 될 수 있다. 처음에 도시 이름으로 하려다가 어차피 다시 돌아올 수도 있는데 무슨 짓인건지 싶어서, 그리고 인덱스별로 나눌 수가 없어서 티켓 번호 대로 visited 배열을 처리해야겠단 생각을 했다.
그리고 우선 방문처리를 한 후 그 위치 기준으로 보았을 때 출발할 수 있는 티켓이 있고 그 티켓을 쓰지 않았다면 한번 방문해보는 방식은 똑같다.
만약에 방문을 했는 데 쭉 끝까지 갈 수 있다면? Recursive 하게 탐색 처리를 할 것이고 ticketIndex == ticket.size()조건이 충족되는대로 True 가 반환될것이다. 그게 아닌이상 false 처리가 된다. 가능한 경우들을 다 뒤져보는 것이다.

최종적으로 가능한 경로가 answer에 저장된 채 프로그램은 종료된다. 탐색 기준을 도시로 잡을것인가, 티켓으로 잡을것인가만 생각해보면 어렵지 않은 문제다.