programmers [C++] : 여행경로

programmers.co.kr/learn/courses/30/lessons/43164#qna

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

문제 설명

---

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

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 출력하시오.

 

제한사항

- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.

- 주어진 공항 수는 3개 이상 10,000개 이하입니다.

- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.

- 주어진 항공권은 모두 사용해야 합니다.

- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

 

접근 방법

---

1. 처음 ICN 공항을 찾는다.

2. 차례로 [도착지<>출발지] 가 연결되도록 Dfs를 진행한다.

 

 

코드

---

#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool visited[10001][2];
vector<string> answer;
vector<string> real_ans;

void dfs(int idx,int sum,int s,vector<vector<string>> tickets){
    if(sum==s){
        answer.push_back(tickets[idx][1]);
        //compare two value
        if(real_ans.empty()){
            real_ans=answer;
        }
        else{
            bool ischange=false;
            for(int i=0;i<real_ans.size();i++){
                if(real_ans[i]>answer[i]){
                    ischange=true;
                    break;
                }
                else if(real_ans[i]<answer[i]) break;
            }
            if(ischange) real_ans=answer;
        }
        answer.pop_back();
        return;
    }
    else{
        for(int i=0;i<s;i++){
            if(visited[i][0]!=true){
                if(tickets[idx][1]==tickets[i][0]){
                    answer.push_back(tickets[i][0]);
                    visited[i][0]=true;visited[i][1]=true;
                    dfs(i,sum+1,s,tickets);
                    visited[i][0]=false;visited[i][1]=false;
                    answer.pop_back();
                }
            }
            
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    
    int Size=tickets.size();
    
    memset(visited,false,sizeof(visited));
    for(int i=0;i<Size;i++){
        if(tickets[i][0]=="ICN"){
            answer.push_back(tickets[i][0]);
            visited[i][0]=true;visited[i][1]=true;
            //idx, sum, Size, Tickets vec
            dfs(i,1,Size,tickets);
            visited[i][0]=false;visited[i][1]=false;
            answer.pop_back();
        }
        
    }
    //real _ans 출력
    return real_ans;
}

funny algorithm 0_<