[프로그래머스] 여행경로 (문자열, BFS) [C++]

programmers.co.kr/learn/courses/30/lessons/43164

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

주어진 경로대로 탐색을 하면 되는데, 노드가 문자열이기도 하고 숫자로 매핑을 어떻게 해야 할지 몰라서 너무 복잡하게 풀었다.

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

int check[10001][10001];
map<string, int> m;
vector<int> v[10001]; // int끼리 연결관계
vector<string> vs;
vector<string> answer;
int n;

bool compare(int& a, int& b) {
    return vs[a] < vs[b];
}

void DFS(int start) {
    answer.push_back(vs[start]);

    if (answer.size() == n + 1)
        return;

    for (int i = 0; i < v[start].size(); i++) {
        int next = v[start][i];
        if (check[start][next]) {
            check[start][next]--;
            DFS(next);
            if (answer.size() == n + 1)
                return;
            check[start][next]++;
            answer.pop_back();
        }
    }

}

vector<string> solution(vector<vector<string>> tickets) {
    n = tickets.size();
    int cnt = 1;
    m["ICN"] = 0;
    vs.push_back("ICN");
    for (int i = 0; i < tickets.size(); i++) {
        string from = tickets[i][0];
        string to = tickets[i][1];

        if (from != "ICN" && !m[from]) {
            m[from] = cnt;
            cnt++;
            vs.push_back(from);
        }
        if (to != "ICN" && !m[to]) {
            m[to] = cnt;
            cnt++;
            vs.push_back(to);
        }
        v[m[from]].push_back(m[to]);
        check[m[from]][m[to]]++;
    }

    for (int i = 0; i <= cnt; i++) {
        sort(v[i].begin(), v[i].end(), compare);
    }

    DFS(0);

    return answer;
}

코드를 설명하자면

1. map을 통해 각 경로 이름에 숫자를 매핑해주었다. (ICN부터 시작이니 0번을 넣어주었다.)

2. 티켓들을 순환하면서 새로 나오는 경로의 이름에 역시 숫자를 붙여주었다.

3. 그리고 그래프 순회를 하듯이 2차원 벡터에 매핑한 숫자들을 from, to로 해서 연결 정보를 저장했다.

4. 알파벳순으로 탐색을 해야 하므로 2차원 벡터들을 map의 문자열로 sort 해주었다.

5. DFS에서는 출발-도착의 탐색 여부를 탐색해주면서, 모든 티켓을 다 써야 한다는 조건 때문에 개수를 체크해주었다.

6. 만약 더 이상 갈 경로가 없지만 정답 개수가 티켓 하고 맞지 않다면 방문 여부를 해제해주면서 백 트래킹 해주었다.

7. 탐색 완료 & 개수가 일치하면 끝내주었다.

 

너무 복잡하다 ㅜㅜ

 

따라서 다른 분들의 코드를 참고해보았다.

 

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

using namespace std;
    vector<string> answer;
int DFS(string from, vector<vector<string>> & ticket, vector<bool> &visited, int depth){
    answer.push_back(from);
    if(depth == ticket.size()){
        return true;
    }
    
    for(int i = 0 ; i < ticket.size() ; i++){
        if(ticket[i][0] == from && !visited[i]){
            visited[i] = true;
            bool flag = DFS(ticket[i][1], ticket, visited, depth+1);
            if(flag){
                return true;
            }
            visited[i] = false;
        }
    }
    answer.pop_back();
    return false;
}



vector<string> solution(vector<vector<string>> tickets) {

    vector<bool> visited(tickets.size(), false);
    sort(tickets.begin(), tickets.end());
    DFS("ICN", tickets, visited, 0);

    return answer;
}

우선, 티켓 자체를 정렬해주어서 무조건 우선순위가 먼저인 티켓을 사용하게 해 주고

"ICN"부터 탐색을 시작해준다.

DFS에서는 티켓수만큼 사용해야 하므로 depth를 이용해주고, 티켓들을 순회하면서 만약 from이 일치하고 사용하지 않은 티켓이라면 사용해준다.

재귀를 이용해서 티켓을 다 사용하면 true, 아니면 false를 통해 방문을 해제해주고 정답에 넣은 경로도 빼주면서 진행을 해준다.