여행경로

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

프로그래머스

 

풀이 :

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

using namespace std;

//            티켓 목록,   티켓 번호,  찾을 글자
bool DFS(const vector<vector<string>>& _Tickets, string _Curstring, vector<bool>& _Visited, vector<string>& _Answer)
{
    // +1 이 같으면 재귀를 탈출해야한다.  같을때 탈출하면 마지막요소를 체크하지 못한다.
    if (_Answer.size() == _Tickets.size() + 1)
    {
        return true;
    }

    for (size_t i = 0; i < _Tickets.size(); i++)
    {
        if (_Tickets[i][0] == _Curstring && _Visited[i] == false)
        {
            _Visited[i] = true;
            _Answer.push_back(_Tickets[i][1]);

            // DFS의 리턴값을 bool로하여 모든 요소의 체크가 끝났음을 리턴할때 true로 리턴하여 되돌아간다.
            // 끝마쳤을때 나머지도 다 끝마친다.
            if (true == DFS(_Tickets, _Tickets[i][1], _Visited, _Answer))
            {
                return true;
            }

            _Visited[i] = false;
            _Answer.pop_back();
        }
    }

    // 모든 항목을 살펴보지 못했으므로 false로 계속 탐색한다는 의미.
    return false;
}


vector<string> solution(vector<vector<string>> tickets)
{
    vector<string> answer;
    vector<bool> VisitedTicket(tickets.size(), false);

    // 2중배열을 sort하게되면 첫번째요소를 기준으로 정렬하게되고 첫번째 요소가 같다면
    // 이후에는 두번째요소를 기준으로 정렬을 하게 된다.
    sort(tickets.begin(), tickets.end());

    answer.push_back("ICN");
    DFS(tickets,"ICN", VisitedTicket, answer);


    return answer;
}

 

코드 설명 :

1. 사전순 정렬:
   • solution함수에서 티켓 목록을 사전순으로 정렬합니다. 이렇게 하면 DFS탐색 시 알파벳 순으로 경로를 탐색할 수 있습니다.
2. DFS함수:
   • DFS함수에서는 현재 경로를 저장하는 answer를 인자로 받아서 경로가 완성될 때까지 재귀적으로 호출합니다.
   • 현재 경로의 크기가 tickets.size() + 1 이 된다면, 이는 모든 티켓을 사용하여 경로가 완성된 것이므로 true를 반환하여 재귀 함수를 종료하게 됩니다.
3. 백트래킹:
   • 티켓을 사용한 후 경로가 완성되지 않으면 visited상태를 되돌리고 경로에서 해당 목적지를 제거합니다. pop_back()을 통해 제거, 이 과정은 백트래킹을 통해 다른 경로를 탐색할 수 있도록 합니다.
   • pop_back()을 통해 요소를 제거하지 않으면 answer에 데이터가 누적되어 전혀 다른 답을 도출하게 된다.