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

 

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

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

[문제 풀이]

DFS를 이용하여 문제를 풀었습니다.

 

이 문제는 공항을 잇는 경로들이 주어지고 모든 공항을 잇는 경로 중 알파벳 순이 가장 빠른 경로를 찾는 문제입니다. 문제를 푸는 방법은 주어진 경로들을 알파벳 순으로 정렬하여 알파벳 순으로 경로들을 확인하면서 가장 먼저 나오는 경로를 찾는 방법입니다.

 

코드 설명

• tickets 백터를 알파벳 순으로 정렬합니다.
• 정렬 후 DFS 함수를 호출합니다.
• DFS 함수의 매개변수로 들어온 from(출발 경로)을 temp(전체 임시 경로)에 넣어 줍니다.
• 경로가 다 이어져있으면 answer에 temp를 넣어주고 true를 반환합니다.
• 아직 이어지지 않았다면 tickets 배열을 순회하며 방문하지 않았으면서 시작 지점이름이 from과 같은 것이면 DFS를 호출합니다. 배열의 끝까지 가도 이어지지 않았다면 false를 호출하고 from을 temp에서 빼줍니다.

[코드]

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

using namespace std;

bool DFS(string from, vector<vector<string>>& tickets, vector<bool>& visit, 
	vector<string>& temp, vector<string>& answer, int cnt){
    
    temp.push_back(from);
    
    if(cnt == tickets.size()){
        answer = temp;
        return true;
    }
    
    for(int i = 0; i < tickets.size(); i++){
        if(tickets[i][0] == from && visit[i] == false){
            visit[i] = true;
            
            bool chk = DFS(tickets[i][1], tickets, visit, temp, answer, cnt+1);
            
            if (chk) return true;
            
            visit[i] = false;
            
        }
    }
    temp.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer, temp;
    vector<bool> visit(tickets.size(), false);
    
    sort(tickets.begin(), tickets.end());
    DFS("ICN", tickets, visit, temp, answer, 0);
    
    return answer;
}