[C++][Programmers][DFS/BFS] 여행경로

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

프로그래머스

주어진 항공편을 모두 사용하는 경로를 찾으면 된다. 경로가 여러개면 알파벳 순서가 빠른 경로 한개를 출력하면 된다.

 

 

*해결법

주어진 항공편을 모두 사용해야 하므로, ICN부터 출발지점 -> 도착지점을 DFS로 탐색했다.

이 때, 경로를 저장해야 하므로 answer 는 stack(vector) 후입선출 구조를 사용했다.

 

구체적인 방법은 출발지점으로 지정한 문자와 같은걸 찾고, 도착지점을 다시 출발지점으로 설정하며 모든 항공편을 다 사용할 때까지 반복하면 된다. DFS 탐색시 depth 를 같이 보내서 최소 depth 인지를 판단해야 한다.

 

 

*알아둘 것

1) 벡터 선언 및 초기화

vector<bool> isVisited(tickets.size(), false);

2) vector 값 넣고 빼기

answer.push_back(airport);

answer.pop_back();

 

 

*코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> isVisited(tickets.size(), false);
    
    //가능한 경로가 2개 이상일 때 알파벳 순서가 앞서는 경로를 return 해야 하므로 미리 정렬.
    sort(tickets.begin(), tickets.end());
    //DFS 탐색으로 모두 탐색하는 경로 찾기
    DFS("ICN", tickets, answer, isVisited, 0);
    
    return answer;
}