링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43164
문제 설명
주어진 항공권을 모두 이용하여 여행결로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
티켓이 담긴 2차원 배열 tickets가 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하시오.
제한조건
* 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
* 주어진 공항 수는 3개 이상, 10,000개 이하입니다.
* ticket [a, b]는 a공항에서 b공항으로 가는 항공권입니다.
* 주어진 항공권을 모두 사용해야합니다.
* 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 우선시합니다.
* 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
아이디어
1. 어떤 항공권이 어디로 갈 수 있는지 체크합니다. a > {b, c, d ..}
2. 경로가 여러개일 경우 알파벳 순서가 앞서는 경우가 return 되니, 항공권을 알파벳 순서로 정리합니다.
3. ICN을 시작으로 앞에서부터 탐색하면서 모든 항공권을 사용할 수 있는 경우가 생기면 종료합니다.
코드
#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
map<string, vector<string>> table;
map<string, vector<bool>> used;
vector<string> route;
int cnt = 0;
int ticketSize;
vector<string> answer;
void DFS(string cur)
{
route.push_back(cur);
cnt++;
if(cnt == ticketSize){
if(answer.empty()) answer = route;
return ;
}
for(int i = 0; i < table[cur].size(); i++)
{
if(!used[cur][i])
{
used[cur][i] = true;
DFS(table[cur][i]);
used[cur][i] = false;
}
}
cnt--;
route.pop_back();
return ;
}
vector<string> solution(vector<vector<string>> tickets) {
ticketSize = tickets.size()+1;
for(auto ticket : tickets)
{
table[ticket[0]].push_back(ticket[1]);
used[ticket[0]].push_back(false);
}
for(auto &line : table)
{
sort(line.second.begin(), line.second.end());
}
DFS("ICN");
return answer;
}
피드백
1. 주어진 항공권을 모두 쓰는게 아니라 출발하고 돌아오는 가장 빠른 루트인줄 알고 문제를 이상하게 풀었습니다...
'알고리즘' 카테고리의 다른 글
프로그래머스 - 도넛과 막대 그래프 (0) | 2024.03.09 |
---|---|
프로그래머스 - PCCP 기출문제 2(250136) (0) | 2023.12.31 |
프로그래머스 - 표 병합(150366) (0) | 2023.08.29 |
프로그래머스 - 합승 택시 요금(72413) (0) | 2023.08.29 |
프로그래머스 - 상담원 인원(214288) (0) | 2023.08.24 |