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

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

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

1. 주의할 점

- 지문을 정확히 읽어야 한다 (만일 경로가 여러개일 경우, 알파벳 순서가 앞선것 출력)

- 알파벳 순서에 대한 처리를 수행한다

 

2. 구현

- 티켓에 포함된 공항명을 Map<String,Int>에 담는다. 또한, 경로에 대한 정보를 V[출발공항 번호]에 '도착공항'을 담는다

- V[] 벡터에 대해 알파벳 숫자가 앞선 순서대로 정렬한다

- DFS() 함수를 통해 해당하는 경로를 찾는다

- 현재 공항에 대해 사용하지 않은 티켓이 있다면 해당 티켓을 사용하여 경로를 검색한다. 이때, 여러 티켓이 존재할 경우, 정렬로 인해 알파벳 순서대로 이동하지만 해당 경로가 오답일 수 있다

["ICN","AB"],["ICN","AC"],["AC","ICN"]

: ICN → AB → 다음 공항이 존재x  ∴ 해답이 아니다(∵모든 티켓을 사용하지 않았으므로)

: ICN → AC → ICN →AB : 해답

- 모든 조건을 만족하는 경로를 찾은 경우, 더 이상 탐색을 수행하지 않도록 Finish 변수를 통해 DFS()를 통제한다

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
struct info{
    string str;
    bool used=false;
};
bool cmp(info &a,info &b){
    return a.str < b.str;
};

info tmp;
vector<info> v[10001];
int len;
vector<string> answer;
bool finish=false;    
map<string,int> m;

void dfs(int idx){
    if(finish) return;
    if(idx>len){
        finish=true;
        return;
    }
    string cur = answer[idx-1];
    int val = m[cur];       //현재 지점을 숫자로
    for(int i=0;i<v[val].size();i++){
        if(v[val][i].used) continue;
        v[val][i].used=true;
        string next = v[val][i].str;
        answer.push_back(next);
        dfs(idx+1);
        if(finish) return;
        answer.pop_back();
        v[val][i].used=false;
    }
}

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

    int tot=0;
    len = tickets.size();
    
    for(int i=0;i<tickets.size();i++){
        string s1 = tickets[i][0];
        string s2 = tickets[i][1];
        if(m[s1]==0) m[s1]=++tot;
        if(m[s2]==0) m[s2]=++tot;
        tmp.str = s2;
        v[m[s1]].push_back(tmp);
    }
    for(int i=1;i<=tot;i++){
        sort(v[i].begin(),v[i].end(),cmp);
    }
    answer.push_back("ICN");
    dfs(1);    
    return answer;
}