[프로그래머스 lv3] 여행경로 풀이

해설

여러 경로가 있을 때, 사전 순으로 목적지를 선택해야 하므로 tickets을 정렬시킨다.

 

흔히 dfs는 노드를 중심으로 방문여부를 체크하고 탐색을 진행한다.

그런데, 이 문제의 경우 노드가 아닌 티켓을 중심으로 탐색을 진행해야 한다.

노드의 경우 여러번 방문이 가능하기 때문에, 티켓의 사용여부를 체크하면서 다음 티켓을 탐색해야 한다.

 

현재 방문 노드가 x일 때, 출발지를 x로 하는 티켓 중 아직 체크되지 않은 티켓을 사용할 수 있다.

tickets[i]를 사용할 때, tickest[i][1]이 다음 목적지가 되므로 tickets[i][1]을 출발지점으로 하는 dfs를 수행하면 된다.

가능한 깊이까지 모두 탐색하였을 때, 모든 티켓을 사용하지 않았다면 다음 루트를 고려해야 하므로 flag를 사용하여 모든 티켓을 사용하였는지 여부를 확인한다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<string> ans;
vector<bool> visited(100000005, false);
bool flag;

void dfs(string x, int cnt, const vector<vector<string>>& tickets) {
    
    ans.push_back(x);
    if (cnt >= tickets.size()) flag = true;
    
    for (int i=0; i<tickets.size(); i++) {
        if (visited[i] || tickets[i][0] != x) continue;
        visited[i] = true;
        dfs(tickets[i][1], cnt+1, tickets);
        if (!flag) {
            visited[i] = false;
            ans.pop_back();
        }
    }
}

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

 

 

팁

재귀를 활용하여 모든 경우를 확인해야 할 때 다음과 같은 포맷의 백트래킹 코드를 사용하면 좋다.

 

void dfs(string x, int cnt, const vector<vector<string>>& tickets) {
    
    ans.push_back(x);
    if (cnt >= tickets.size()) {
        for (auto x : ans) cout<<x<<" ";
        cout<<endl;
    }
    
    for (int i=0; i<tickets.size(); i++) {
        if (visited[i] || tickets[i][0] != x) continue;
        visited[i] = true;
        dfs(tickets[i][1], cnt+1, tickets);
        //다음 경로로 가는 경우를 탐색하기 위하여 이전에 처리해주었던 부분 삭제(복구)
        visited[i] = false;
        ans.pop_back();
    }
}

 

이 문제에서는 모든 경우가 아닌 사전 순으로 앞서는 첫번째 경우만 구하라고 했으므로,  cnt >= ticket.size()인 경우를 하나 발견하면 flag를 변경하여 다음 경로를 탐색하지 않도록 하면 된다.