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

문제 링크

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

 

 

 

풀이

주어진 조건을 잘 봐야겠다는 생각이 드는 문제였다.

[조건]

1. 주어진 항공권 모두 사용

2. 가능한 경로가 다수 개일 경우, 알파벳 순서가 앞서는 경로

 

조건 1은 깊이(depth)를 이용하여 모두 방문했다는 것을 인지했다.

조건 2는 미리 도착지에 대해 내림차순하여 마지막으로 갱신되는 것이 알파벳 순서가 앞서는 것으로 처리했다.

 

++ 그리고 만약에 중간에 경로가 불가능해지는 것에 대해서

탈출 키워드 '#'을 사용하여 return 되는 것이 '#'이라면 자신을 호출했던 함수에 대해 조건으로 통과되게 만들었다.

if(next.back() == '#') continue;    --- 해당 문장

 

// bool cmp()

 

- 도착지에 대해 내림차순 정렬하는 조건 비교 함수다.

결국 모두 방문하더라도 ""을 return 하므로 도착지에 대해 return이 된다.

따라서, 도착지에 대해 내림차순 정렬

 

// string dfs()

 

1) 먼저 매개변수를 보면, tickets 배열과 visit 배열은 참조자(&)를 사용하여 시간을 대폭 단축시킨다.

실제로 테스트 돌려보면 5~6배 차이납니다.

-> 이유는 매번 복사생성자를 통한 생성이 자료 크기가 커질수록 시간이 많이 소비된다.

1.1) 나머지 매개변수 string정도는 써도 되지만 depth는 primitive 자료형이라 조금 불편하게 사용해야 해서 Skip!!

 

2) 마지막 모두 방문했을 경우의 탈출 조건은 depth == tickets.size()로 구현(얼마나 깊게 들어갔는지)

 

3) 방문은 true에서 다음 인덱스를 위해 false로 바꿔준다.

 

4) 탈출 키워드 '#' 이용: 마지막 문자가 '#'이면 continue로 통과

- 경로를 찾기 위해 tickets를 순회하다가 경로가 없다면(아직 모두 방문X) '#'을 return하게 된다.

그럼 함수 스택에 top에서는 '#'을 보고 처리하고 또, 다음 top에서는 '#'을 보고 처리하는 식으로 동일하게 처리된다.

 

ex) A가 B를, B가 C함수를 호출했을 경우,

C가 '#'을 return하면

B가 '#'을 받게 되어 '#'을 처리하게 되고,

A도 마찬가지로 B로부터 '#'을 받아 처리하게 된다.

 

5) ('#'으로 초기화돼있던)path 변수에 도착지를 갱신한다.

- 도착지에 대해 내림차순 정렬돼 있으므로 마지막으로 path에 갱신된 것이 알파벳 순서가 앞서는 경로다.

 

// solution

 

// init

1) 사전 반대순으로 정렬(<algorithm>의 stable_sort()이용: 합병정렬)

2) 방문 배열 선언 및 초기화

3) path

 

// process

1) 처음에는 "ICN"으로 처리하기 위해 solution 함수에도 반복문을 수행한다.

2) dfs와 같은 로직

 

// sub

1) path는 string으로 저장되었으므로 split해줘야 한다.

2) 초기 "ICN"을 answer 배열에 넣어준다.   --- 도착지에 대해 path를 할당하고 리턴했으므로

3) 이후 i+=3을 하면서 substr을 이용하여 answer에 넣어준다.

 

return answer;

 

 

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

using namespace std;

// 항상 "ICN" 공항에서 출발
// 항공권 정보가 담긴 2차원 배열 tickets
// 주어진 항공권 모두 사용
// 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로

// tickets의 각 행 [a, b]는 a에서 b가는 항공권

bool cmp(vector<string> s1, vector<string> s2){
    return s1[1] > s2[1];       // 도착지에 대해 내림차순
}

string dfs(vector<vector<string>>& tickets, vector<bool>& visit, string cur, int depth){
    if(depth == tickets.size()) return "";      // 모두 방문
    
    // init
    string path = "#";          // 탈출 키워드
    
    // process
    for(int i=0; i<tickets.size(); i++){
        if(visit[i] || cur != tickets[i][0]) continue;          // 방문했거나 경로가 불가하거나
        string next = tickets[i][1];        // 다음 도착지
        visit[i] = true;        // 방문 표시
        next += dfs(tickets, visit, next, depth+1);  // 제일 마지막은 ""를 리턴하므로
        visit[i] = false;       // 다음 인덱스를 위한 방문 해제
        if(next.back() == '#') continue;    // 맨 뒤 문자가 탈출 키워드면 해당 경로는 불가
        path = next;        // 도착지 할당
    }
    return path;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    
    // init
    stable_sort(tickets.begin(), tickets.end(), cmp);       // 사전 반대순
    vector<bool> visit(tickets.size(), false);
    string path = "";
    
    // process
    for(int i=0; i<tickets.size(); i++){
        if(tickets[i][0] != "ICN") continue;
        string next = tickets[i][1];        // 도착지
        visit[i] = true;        // 방문 표시
        next += dfs(tickets, visit, next, 1);  // dfs, depth: 0 -> 1
        visit[i] = false;       // 다음 인덱스를 위해 방문 해제
        if(next.back() == '#') continue;        // 맨 뒤 문자가 탈출 키워드면 해당 경로는 불가
        path = next;
    }
    
    // sub
    answer.push_back("ICN");        // 첫 출발 넣어주기
    for(int i=0; i<path.length(); i+=3){ 
        answer.push_back(path.substr(i, 3));    // 3글자씩
    }
    
    return answer;      // 방문하는 공항 경로 리턴
}