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

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=cpp 

프로그래머스

 

이번 문제는 dfs 문제였습니다.

 

 

 

 

 

📝 문제 풀이

1. "ICN" 공항에서 출발하는 항공권이면 path 벡터에 "ICN" 삽입

2. dfs 수행

• 항공권을 사용했다는 의미로 visited[idx] = true
• path 벡터에 도착 공항 삽입
• 주어진 항공권을 다 사용했다면, 가능한 경로 벡터 paths에 path 벡터 삽입
• 사용하지 않은 항공권이고, 현재 항공권의 도착 공항과 사용하려는 항공권의 시작 공항이 같으면 dfs 수행
• dfs 수행이 끝난 후, 항공권을 다시 사용할 수 있도록 visited[i] = false

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#include <algorithm>
#define MAX 10000

using namespace std;

vector<bool> visited(MAX);
vector<vector<string>> paths;

void DFS(int idx, vector<vector<string>> &tickets, vector<string> path) {
    visited[idx] = true;
    path.push_back(tickets[idx][1]);
    
    // 주어진 항공권을 모두 사용했다면
    if (path.size() == tickets.size() + 1) {
        paths.push_back(path);
        return;
    }
    
    for (int i=0; i<tickets.size(); i++) {
    	// 사용하지 않은 항공권이고, 현재 항공권의 도착 공항과 출발 공항이 같다면
        if (!visited[i] && tickets[idx][1] == tickets[i][0]) {
            DFS(i, tickets, path);
            visited[i] = false;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    for (int i=0; i<tickets.size(); i++) {
        vector<string> path;
        visited = {0, };
        
        if (tickets[i][0] == "ICN") {
            path.push_back("ICN");
            DFS(i, tickets, path);
        }
    }
    
    sort(paths.begin(), paths.end());           
    
    return paths[0];
}

 

프로그래머스 - 결과 화면