프로그래머스 LV 3 _ 여행 경로

 

0️⃣ 문제링크

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

프로그래머스

3️⃣ 내 코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
vector<string> answer; //경로 저장 할 answer
bool visited[10001]; //티켓 쓴 거 표시
bool flag = false; //모두 순회 했는지 체크할 bool
int cnt; //카운트
 
void DfS(string cur, const vector<vector<string>> tickets)
{
    if (cnt == tickets.size()) flag = true;
 
    answer.emplace_back(cur);
 
    for (int i = 0; i < tickets.size(); i++)
    {
        if (!visited[i] && tickets[i][0] == cur)
        {
            visited[i] = true;
            cnt += 1;
            DfS(tickets[i][1], tickets);
 
            //backtracking
            if (!flag)
            {
                answer.pop_back();
                visited[i] = false;
            }
 
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    DfS("ICN", tickets);
    return answer;
}

4️⃣ 새로 알게된 점 또는 참고한 자료

https://gyyeom.tistory.com/43

https://eunchanee.tistory.com/93

DFS로 푸는 것과 백트래킹을 사용해야하는 것까지는 유추가 되나 백트래킹 구현에 있어서 게속해서 막힌다.

전에도 보석쇼핑 문제에서도 백트래킹을 구현하는 구간에서 막혔었는데 주말이든 시간을 내어서 백트태킹구현하는 법을 공부해야겠다.