[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 여행경로

 

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 여행경로

 

문제 설명

가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 return 해야하기 때문에

tickets배열을 우선 정렬한다.

 

정렬한 tickets배열을 DFS로 돌고, tickets를 다 돌았을 경우가 답이 된다.

만약 tickets를 다 돌기도 전에 DFS가 끝나게 되면 백트래킹으로 마지막을 하나씩 가지치기 하면서 답을 구한다.

 

 

제한사항

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

 

 

 

풀이 ( 정답 )

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

using namespace std;

vector<string> result;
vector<vector<string>> ticket;
bool visited[100001] = {false, };
bool isEnd = false;

void DFS(string departure, int count) {
    result.push_back(departure);
    
    if(count == 0) isEnd = true;
    
    for(int i = 0; i < ticket.size(); i++) {
        if(visited[i]) continue;
        if(ticket[i][0] == departure) {
            visited[i] = true;
            DFS(ticket[i][1], count-1);
            if(!isEnd) {
                visited[i] = false;
                result.pop_back();
            }
        }
    }
}

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