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

1. 문제

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

프로그래머스

 

 

2. 풀이

2-1. 문제 읽고 이해하기

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

 

<주어지는 것>

항공권 정보가 담긴 2차원 배열 tickets

 

<목표>

방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 모든 공항은 알파벳 대문자 3글자
• 공항 수는 3개 이상 10,000개 이하
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

2-2. 재정의와 추상화

tickets [a, b]는 a 공항에서 b공항으로 가는 항공권이 있다: [a, b]는 a→b가 가능하다는 의미. 출발지와 도착지가 정해져 있으므로 방향 그래프. 다시 말해 "공항=노드", "tickets=간선"으로 해석이 가능하다.

 

2-3. 계획 세우기

출발은 항상 ICN 공항에서 한다. 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 해야 하므로 도착지를 기준으로 오름차순 정렬 한다. 첫 번째 항공권이 ICN 항공이라는 보장이 없으므로 for문을 돌며 출발지가 ICN인 항공권의 start idx를 찾는다.

start idx부터 시작하여 start→end(start)→end(start)→end(start)→end(start)→end 이렇게 들어가야 하므로 dfs(깊이 우선)

모든 항공권을 다 쓰는 것이 문제의 조건이기 때문에 같은 공항을 여러 번 방문할 수 있다. 한 번 쓴 항공권은 여러 번 쓸 수 없으므로 항공권을 사용했는지 아닌지를 visited 배열로 표현해야 한다.

 

3. 코드

3-1. 틀린 코드

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

using namespace std;

bool cmp(vector<string> &a, vector<string> &b){
    if(a[1]==b[1]){
        return a[0]<b[0];
    }
    return a[1]<b[1];
}

void dfs(int idx, vector<bool> &used, vector<string> &route, const vector<vector<string>> &tickets){
    string from = tickets[idx][1];
    route.push_back(from);
    
    for(int i=0; i<tickets.size(); i++){
        // 도착지에서 출발해야 하므로 from과 start(tickets[i][0])가 동일해야 한다.
        string start = tickets[i][0];
        // 사용한 티켓은 또 사용할 수 없다.
        if(start == from && !used[i]){
            used[i]= true;
            dfs(i, used, route, tickets);
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end(), cmp);
    
    // 티켓 사용 여부
    vector<bool> used(tickets.size(), false);
    
    // ICN 공항에서 시작해야 하므로 ICN 공항이 몇 번째 티켓인지 찾아야 한다.
    int startIdx = -1;
    for(int i=0; i<tickets.size(); i++){
        string start = tickets[i][0];
        if(start == "ICN"){
            startIdx = i;
            break;
        }
    }
    
    // startIdx에서 시작
    used[startIdx] = true;
    answer.push_back(tickets[startIdx][0]);
    dfs(startIdx, used, answer, tickets);
    
    return answer;
}

틀린 이유가 뭔지 모르겠어서 질문 게시판을 봤다.

https://school.programmers.co.kr/questions/80077

 

코딩테스트 연습 힌트 모음집

https://school.programmers.co.kr/learn/courses/14743/lessons/118891

 

3-2. 정답 코드

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

using namespace std;

vector<string> answer;
bool found = false;

// DFS + 백트래킹
void dfs(string from, vector<vector<string>> &tickets, vector<bool> &used, vector<string> route) {
    // 모든 항공권을 사용한 경우
    if (route.size() == tickets.size() + 1) {
        answer = route;  // 경로 저장
        found = true;    // 정답을 찾았음을 표시
        return;
    }

    for (int i = 0; i < tickets.size(); i++) {
        if (!used[i] && tickets[i][0] == from) {  // 사용하지 않은 티켓이면서 출발지가 일치하는 경우
            used[i] = true;
            route.push_back(tickets[i][1]);
            dfs(tickets[i][1], tickets, used, route);
            if (found) return;  // 정답을 찾았다면 더 이상 탐색하지 않음
            used[i] = false;
            route.pop_back();
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    // 티켓을 알파벳 순으로 정렬
    sort(tickets.begin(), tickets.end());

    vector<bool> used(tickets.size(), false);
    vector<string> route;
    route.push_back("ICN");  // 시작점 고정

    dfs("ICN", tickets, used, route);

    return answer;
}