프로그래머스 문제 - 여행경로

프로그래머스 여행경로 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

주어진 항공권을 이용하여 여행경로를 짜려고 하며 항공권 정보가 담긴 2차원 배열이 주어집니다.
모든 공항은 알파벳 대문자 3글자로 이루어지며, 공항의 수는 3~10000개 입니다.
항공권 정보가 담긴 배열의 각 행[a, b]는 a공항에서 b공항으로 가는 항공권이라는 의미입니다.
주어진 항공권은 전부 사용해야 하며, 가능한 경로가 있을 경우 알파벳 순서가 앞서는 경로로 가야 합니다.
위의 사항에 맞는 경로값을 return해야 합니다.

문제 풀이

여러 여행경로를 우선 탐색으로 찾아서 알파벳 순서가 더 앞서는 경로를 찾아주면 됩니다.

입력과 들어오는 값들이 string으로 되어 있으니 빠르게 찾아내기 위하여 unordered_map을 사용해주었으며, key값은 현재 공항 value값은 공항에서 이동할 수 있는 공항들을 배열로 저장해두었습니다.

항공권들을 unordered_map에 전부 저장해준 후, 무조건 시작은 ICN으로 시작하여 갈 수 있는 항공으로 전부 체크해주면 됩니다.
주어진 티켓 수+1만큼의 경로가 있는 상황이 항공권을 전부 사용한 상태이므로 이후에 나오는 값들과 비교하며 알파벳 순서가 더 앞서는 경로로 저장해주고 return시키면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

unordered_map<string, queue<string>> airportTickets;
vector<string> answer;
int cnt;

void solve(string curAirport, vector<string> result, unordered_map<string, queue<string>> Tickets)
{
    //현재 있는 공항을 넣어줌
    result.push_back(curAirport);
    //만약 현재 있는 공항에서 다른 곳으로 이동이 가능할 경우
    auto iter = Tickets.find(curAirport);
    if(iter != Tickets.end())
    {
        if(!iter->second.empty())
        {
            //갈 수 있는 곳을 한곳씩 가보며 길을 찾음
            int qSize = iter->second.size();
            for(int i = 0; i < qSize; i++)
            {
                string str = iter->second.front();
                iter->second.pop();
                solve(str, result, Tickets);
                iter->second.push(str);
            }
        }
    }
    //만약 모든 항공권을 사용했을 경우
    if(result.size() == cnt)
    {
        //비어있으면 넣어줌
        if(answer.empty())
        {
            answer = result;
        }else
        {
            //하나씩 비교하여 알파벳 순으로 앞선 공항이 있을 경우 바꿔줌
            for(int i = 0; i < answer.size(); i++)
            {
                if(answer[i] > result[i])
                {
                    answer = result;
                    break;
                }else if(answer[i] < result[i])
                {
                    break;
                }
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    
    cnt = tickets.size()+1;
    
    //항공권들을 노드에 연결하듯 배열에 저장해줌
    for(vector<string> v : tickets)
    {
        auto iter = airportTickets.find(v[0]);
        if(iter != airportTickets.end())
        {
            iter->second.push(v[1]);
        }else
        {
            airportTickets.emplace(make_pair(v[0], queue<string>()));
            airportTickets[v[0]].push(v[1]);
        }
    }
    solve("ICN", vector<string>(), airportTickets);
    
    return answer;
}

출저

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