(프로그래머스 C++) Lv3 여행경로

링크 : programmers.co.kr/learn/courses/30/lessons/43164

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

분류 : 깊이/너비 우선 탐색 (DFS/BFS)

 

이 문제는 제한사항들 중에서 서로 충돌하는 포인트가 있다. 

---

• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return합니다. 
• 주어진 항공권은 모두 사용해야 합니다.

---

이 두 조건을 동시에 고려하지 않고 문제를 풀면 아래와 같은 예시에서 충돌이 발생한다. 

---

입력값 : [["ICN", "AAA"], ["AAA", "CCC"], ["AAA", "DDD"], ["DDD", "BBB"], ["BBB", "AAA"]]

출력값 : ["ICN", "AAA", "DDD", "BBB", "AAA", "CCC"]

---

 ["AAA", "CCC"]가 먼저 나왔다고 ICN -> AAA -> CCC로 가버리면 CCC 이후로 갈 수 있는 곳이 없어진다.

즉, 모든 티켓을 활용해야하는 조건을 이수하지 못하게 된다.

 

아닌 경로에 대해서는 다시 돌아가 백 트래킹을 실행해야하는데,

다시 돌아가는 과정에서 코드를 능숙하게 작성하지 못해서 반복적으로 Case 1 에서 실패를 맞이했다.

 

결론은 간단했다. 옳바른 경로가 경우에는 'bool'문을 활용해서 판단해주면 된다.

 

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

using namespace std;
bool ch[10001];
vector<string> answer, ans;

bool dfs(string dep, int num, vector<vector<string>> &tickets, vector<bool> &ch) {
    if (num == tickets.size()) {
        answer = ans;
        return true;
    }
    for (int i = 0; i < tickets.size(); i++) {
        if (tickets[i][0] == dep && !ch[i]) {
            ch[i] = true;
            ans.push_back(tickets[i][1]);
            if (dfs(tickets[i][1], num + 1, tickets, ch)) return true; // 조건 2
            ch[i] = false;
        }
    }
    ans.pop_back(); // 조건2 - (1)
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<bool> ch(tickets.size(), false);
    sort(tickets.begin(), tickets.end()); // 조건 1
    ans.push_back("ICN");
    dfs("ICN", 0, tickets, ch);

    return answer;
}

 

조건1에서 티켓의 오름차순으로 정렬하여 ABC순서로 탐색이 진행하게 해준다.

조건2는 조금 구체적으로 설명해보면 다음과 같다. 

1. 오름차순으로 탐색하여 진행하던 티켓들의 갯수가 맞아떨어지면 (즉, 모든 티켓 사용)
   answer결과에 그동안 쌓아온 티켓들을 누적한 뒤 곧 바로 return true하여 종료한다. 
2. 초반에 언급된 예시처럼 다음에 가야할 경로가 없는 경우, 방문 기록을 취소하며 (ch[i] = false)
   해당 배열에 마지막으로 넣어줬던 티켓을 제거해주고 (조건2-(1)) 
   return false를 한다.