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

문제 링크

이 문제를 이렇게 복잡하게 풀어야 할까..? 여튼 두 번째 예시를 바탕으로 시작해보겠다.

우선 아래와 같이 정보를 저장해주었다.

출발지 공항 이름을 고유 idx와 함께 Map에 저장하였고, 고유 idx를 바탕으로 vector의 각 row에 도착지 공항 이름과 방문 여부를 함께 저장해주었다. 그리고 도착지 공항의 배열들을 알파벳 순서대로 정렬해 주었다.

이렇게 문제에 제시된 정보를 저장해준 다음 "ICN"공항에서부터 DFS를 돌려주었다. 그 전에 모든 도시를 방문할 수 있는 경로의 도시 수는 6개(ticket.size()+1)이고, 그 경로를 담을 수 있는 배열도 하나 생성해 준다.

ICN 공항은 idx가 1이고 ICN 공항에서 갈 수 있는 공항은 ATL과 SFO이다. 먼저 ATL로 날아가 보았다.

ATL 공항은 idx가 3이고, 갈 수 있는 공항은 ICN과 SFO이다. ICN으로 다시 날아가 보겠다.

ICN 공항에서 ATL로 가는 경우는 이미 사용했으므로, SFO로 날아간다. SFO에서는 ATL밖에 갈 수 없으므로 ATL로 가고, 마찬가지로 ATL에서도 남은 선택지가 SFO 밖에 없기 때문에 SFO로 향한다.

이 때 v의 길이가 모든 도시를 방문할 수 있는 경로의 도시 수와 같으므로 v를 저장해두고, DFS를 이어간다. DFS의 중간에 m에 없는 도시 즉, 해당 도시로부터 갈 수 있는 도시가 없는 도시가 나오게 될 경우에는 잘못된 경로이므로 return해야 한다. (이걸 빠뜨려서 테스트케이스 1,2번을 틀렸다.)

코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <iostream>

using namespace std;

vector<pair<string, bool>> myMap[10000];
map<string, int> m;
int dest_length;
queue<vector<string>> pq;

vector<string> v;

bool cmp(pair<string, bool> a, pair<string, bool> b)
{
    if(a.first < b.first) return true;
    else return false;
}

void dfs(string start, int idx)
{
    if(idx==dest_length)
    {
        pq.push(v);
    }
    else
    {
        if(m.find(start)==m.end()) return;
        int cur = m[start];
        for(int i=0;i<myMap[cur].size();i++)
        {
            if(!myMap[cur][i].second)
            {
                myMap[cur][i].second = true;
                v[idx]=myMap[cur][i].first;
                dfs(myMap[cur][i].first, idx+1);
                myMap[cur][i].second = false;
                
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    
    v.resize(tickets.size()+1);
    
    for(int i=0;i<tickets.size()+1;i++)
    {
        v[i]="";
    }
    
    dest_length = tickets.size()+1;
    for(int i=0;i<tickets.size();i++)
    {
        m.insert({tickets[i][0], i});
        myMap[m[tickets[i][0]]].push_back({tickets[i][1], false});
    }
    
    for(int i=0;i<tickets.size();i++)
    {
        sort(myMap[i].begin(), myMap[i].end(), cmp);
    }
    
    v[0]="ICN";
    dfs("ICN", 1);

    return pq.front();
}