[Algorithm] Programmers :: 여행경로

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

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

bool DFS(string start, vector<vector<string>>& tickets, vector<string>& answer, vector<bool>& check, int ticketCount)
{
    answer.push_back(start);
    if (ticketCount == tickets.size()) return true;
 
    for (int i = 0; i < tickets.size(); i++)
    {
        if (tickets[i][0] == start && !check[i])
        {
            check[i] = true;
            bool isSuccess = DFS(tickets[i][1], tickets, answer, check, ticketCount+1);
            if (isSuccess) return true;
            check[i] = false;
        }
    }
 
    answer.pop_back();
    return false;
}
 
 
vector<string> solution(vector<vector<string>> tickets)
{
    vector<string> answer;
    vector<bool> check(100000, false);
 
    sort(tickets.begin(), tickets.end());
    //answer.push_back("ICN");
    DFS("ICN", tickets, answer, check, 0);
 
    return answer;
}

 

3,4년전에 풀었다가 못풀고 다시 풀어 본 문제다. 다시 풀었어도 제대로 못푼 문젠데, 현재 내기준으로 봤을 때, 내가 풀 수 있는 문제보다 한번 더 생각했어야 하는 문제다. 처음에 짠 코드로 제출했더니 3,4번만 통과 하길래 다른 사람 풀이를 봤더니 정확히 그 부분을 짚어줬다.  출처 : https://nanyoungkim.tistory.com/93

[C++] 프로그래머스 Lv.3 - 여행경로(DFS)

 

먼저 이 문제에서 알아둬야할 것은, 인풋값인 tickets를 sort함수로 정렬을 한번 해주는게 좋다는 것이다.

경로가 여러개가 나올 경우, 알파벳순으로 먼저인 경로를 리턴해야하기 때문이다. 한번 정렬을 하고 DFS를 돌리면 순서상 알파벳순서가 빠른곳을 먼저 탐색하기때문에, 처음으로 노드를 다 탐색완료된 경우 그게 정답이다.

 그리고 백트래킹도 조금 섞여있다.  예시로 인풋이 (1,2) (1,3) (3,1) 일 경우, 백트래킹없이 돌리면 1,2에서 2로시작하는 티켓을 찾아야하는데 그런 티켓은 없기때문에 바로 종료되버린다. 그렇기때문에 다시 돌아가서 1,3을 탐색하게 코드를 짜야한다.