[C++]프로그래머스 여행경로

코딩테스트 연습 - 여행경로 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<bool> isUsed(10000000000, false);
bool canReturn = false;
void DFS(int depth, vector<vector<string>> &tickets, vector<string> &answer, string start)
{
    if(depth == tickets.size())
        canReturn = true;
    answer.push_back(start);
    for(int i = 0; i < tickets.size(); i++)
    {
        if(tickets[i][0] == start && !isUsed[i])
        {
            isUsed[i] = true;
            DFS(depth + 1, tickets, answer, tickets[i][1]);
            if(!canReturn)
            {
                answer.pop_back();
                isUsed[i] = false; //DFS뒤에 backTracking
            }
        }
    }
}

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

우선, 갈 수 있는 경로가 여러 개가 있으면 사전순으로 더 앞에오는것을 출력하라고 하였으니 sort한번 해주고 시작한다.

맨 처음 모든 티켓을 다 쓰는 것을 찾는것이므로 DFS를 쓸 것이라 판단하였따.

 

내가 간과한 포인트

(ICN, A) (ICN, B) (B, ICN) 과 같은 경우, 오름차순을 따르지 않게 되는 경우가 생김

(ICN, B, ICN, A) 이렇게.

그럴 때는 backTracking을 이용해서 다시 이전으로 돌아가야하는데, 난 처음에는 백트래킹이 이루어지지 않게 작성하였으므로 for문을 돌고 해당하는 값이 없으면 그냥 DFS문이 끝까지 돌고 종료되었다.

 

그런 불상사를 방지하기 위해,

return될 수 있는 bool형태를 만들어준 후, 이를 만족하지 않았을 경우

DFS 안의 DFS아래쪽에 이미 쌓은 answer을 pop해주고, isUsed도 다시 false로 만들어주는 backTracking이 필요하다.

 

그리고, ICN에서 갈 수 있는 방향이 여러가지이므로 처음 넣을 때 ICN, A를 넣는 것이 아니라 그 for문 자체도 dfs에서 시작해야 하므로 ICN을 시작으로 for문을 돌아야한다.! (오답원인)