[Programmers] 여행경로 c++ (dfs, 문자열 크기 비교)

 

https://school.programmers.co.kr/learn/courses/30/lessons/43164

 

✔ 문제이해

A나라에서  B나라로 갈 수 있는 정보가 적힌 항공권이 2차원 배열로 주어질 때, 모든 항공권을 사용하여 방문하는 경로를 출력하라.

갈 수 있는 방법이 두가지이상일 경우 알파벳순서가 빠른걸로 출력하라.

 

✔ 풀이 + 코드

dfs문제로 모든 경로를 탐색하면 될것이라고 생각했지만 알파벳 순서를 어떻게 보장해야 할지 막막했다.

 

#include <string>
#include <vector>

using namespace std;
int visited[1000000];
string ans_string = "a";

void dfs(vector<vector<string>> &tickets, string cur, string path, int depth) {
    if (depth == tickets.size()) {
        if (path < ans_string) {
            ans_string = path;
        }
        return;
    }

    for (int i = 0; i < tickets.size(); i++) {
        if (cur == tickets[i][0] && !visited[i]) {
            visited[i] = 1;
            dfs(tickets, tickets[i][1], path + tickets[i][1], depth+1);
            visited[i] = 0;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    dfs(tickets, "ICN", "ICN", 0);
    for (int i = 0; i < ans_string.size(); i+=3) {
        answer.push_back(ans_string.substr(i, 3));
    }
    return answer;
}

 

위 코드는 초기값을 "a"로 가지고있던 ans_string과 경로가 담긴 path들을 비교하며 문자로 크기를 비교하며 가장 작은 문자열을 찾는다. (min값을 찾을때 초기값을 987654321로 두는 경우와 같은 경우이다.)

항공권들은 대문자로 주어지기 때문에 소문자인 "a"가 가장 큰 값으로 초기화 할 수 있는것이다. (아스키값)

 

가장 작은 경로는 모든 경로들을 탐색했을때 알파벳 순서로 가는 경로이기 때문에 ans_string에는 모든 항공권을 사용했을 때의 알파벳의 오름차순이 순서인 것이 담기게 된다.

 

 

✔ 피드백

• 문자열로 크기를 비교하는것을 새롭게 알 수 있었다. 잘 기억해 둬야지

✔ reference

프로그래머스 다른사람의 풀이