[Programmers Level3] 여행경로(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

[문제 풀이 사이트]

 

 

프로그래머스

 

 

[문제 설명]

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

[제한 사항]

 

모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

[입출력 예]

 

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

 

[입출력 예 설명]

 

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

[문제 풀이]

 

처음 풀이는 BFS 알고리즘을 사용하여 코드를 작성했다.
바로 제출해서 확인을 했는데 테스트 케이스 1, 2번이 통과가 안됬다.
그래서 분명 이건 맞는데 안되는 케이스가 존재하는 건가 하고 질문하기 게시판을 보았다.

알고보니 사전 순으로 앞선 경로가 있지만 그 경로로 갔을 때 막히는 테스트 케이스가 존재했다.
그래서 해당 내용을 보고 재귀 DFS로 풀어야겠다고 코드를 변경했다.
막히는 경로가 있다면 해당 경로에 대해 방문 취소를 하고 다시 되돌아와서 다른 경로를 찾아야 하기 때문이다.


그렇다면 내가 통과하지 못했던 테스트 케이스로 설명해보도록 하겠다.
(모든 공항은 알파벳 대문자 3글자로 이루어지지만 편의상 아래와 같은 테스트 케이스를 사용)
vector<vector<string>> tickets = {{"ICN", "A"}, {"A", "B"}, {"A", "C"}, {"C", "A"}, {"B", "D"}};

 

필요한 변수는
1. 방문 여부를 기록할 배열이 필요하다.
그래서 티켓의 개수만큼 방문 여부를 기록할 vector를 만들어주고 false로 초기화를 했다.
vector<bool>visitied로 정의

2. 방문한 공항 경로를 기록할 vector가 필요하다.
vector<string> answer로 정의

 

3. 잘못된 경로인지 아닌지 확인할 boolean 변수가 필요하다.

bool isresult로 정의

isresult가 false이면 방문을 취소하고 방문한 공항 경로를 빼준다.

true이면 방문이 잘 됬다는 뜻이다.

 

 

그리고 조건 중에 '만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.'

위 조건으로 인해 sort 함수를 이용하여 '오름차순 정렬' 해주었다.
sort 함수를 사용하면 위 테스트 케이스는 아래와 같이 정렬된다.(사전 순으로 정렬)
vector<vector<string>> tickets = {{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "A"}, {"ICN", "A"}};

그리고 항상 "ICN" 공항에서 출발하기 때문에 방문한 공항 경로 vector인 answer에 "ICN"을 넣고

dfs를 "ICN"에서부터 시작한다.

출발 공항인 "ICN"에서 갈 수 있는 공항을 찾는다. 갈 수 있는 공항은 "A"이기 때문에
방문한 공항 경로 vector인 answer에 "A"를 넣고 {"ICN", "A"} 티켓을 방문처리한다.

 

그리고 "A" 공항에서 갈 수 있는 공항을 찾는다.
"A" 공항에서 갈 수 있는 공항은 {"A", "B"} 이기 때문에
방문한 공항 경로 vector인 answer에 "B"를 넣고 {"A", "B"} 티켓을 방문처리한다.

 

"B" 공항에서 갈 수 있는 공항을 찾는다.
"B" 공항에서 갈 수 있는 공항은 {"B", "D"}이기 때문에
방문하는 공항 경로 vector인 answer에 "D"를 넣고 {"B", "D"} 티켓을 방문처리한다.

 

"D" 공항에서 갈 수 있는 공항을 찾는다.
"D" 공항에서 갈 수 있는 공항은 없다.

🌟 경로가 잘못되었으므로 다시 되돌아와야하고 방문 취소를 해야한다. 🌟

더이상 갈 수 있는 경로가 없을 때 false를 return하고

return 값이 false이면 해당 티켓에 대한 방문 여부를 취소한다.
그리고 방문한 공항 경로 vector인 answer에 넣었던 "D"를 빼준다.

 

 

"B" 공항에서 갈 수 있는 공항을 찾는다.

"B"에서 갈 수 있는 공항은 없다.

🌟 경로가 잘못되었으므로 다시 되돌아와야하고 방문 취소를 해야한다. 🌟

 

더이상 갈 수 있는 경로가 없을 때 false를 return하고

return 값이 false이면 해당 티켓에 대한 방문 여부를 취소한다.
그리고 방문한 공항 경로 vector인 answer에 넣었던 "B"를 빼준다.

 

 

"A" 공항에서 갈 수 있는 공항을 찾는다.

"A" 공항에서 갈 수 있는 공항은 {"A, "C"} 공항이기 때문에

방문한 공항 경로에 "C" 공항을 넣고 {"A, "C"} 티켓을 방문처리한다.

 

 

"C" 공항에서 갈 수 있는 공항을 찾는다.

"C" 공항에서 갈 수 있는 공항은 {"C", "A"} 공항이기 때문에

방문한 공항 경로에 "A" 공항을 넣고 {"C", "A"} 티켓을 방문처리한다.

"A" 공항에서 갈 수 있는 공항을 찾는다.

"A" 공항에서 갈 수 있는 공항은 {"A", "B"} 공항이기 때문에

방문한 공항 경로에 "B" 공항을 넣고 {"A", "B"} 티켓을 방문처리 해준다.

 

 

"B" 공항에서 갈 수 있는 공항을 찾는다.

"B" 공항에서 갈 수 있는 공항은 {"B", "D"} 공항이기 때문에

방문한 공항 경로에 "D" 공항을 넣고 {"B", "D"} 티켓을 방문처리 해준다.

 

 

모든 공항을 다 여행했으므로 true를 리턴한다.

true를 리턴하면 방문이 잘 진행됬다는 뜻이다.

true를 리턴하면서 원래 처음 노드까지 와서 마지막으로 true를 리턴하며 dfs 함수는 종료된다.

그리고 최종적으로 방문한 공항 경로를 return 해주면 된다.

 

 

[최종 코드]

 

[GitHub]

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

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

using namespace std;

vector<bool> visited;
vector<string> answer;
int len;

bool dfs(string cur, vector<vector<string>>& t, int usedtickets) {
    // 탈출 조건 필요
    if (usedtickets == len) {
        return true;
    }

    for (int i = 0; i < len; ++i) {
        if (visited[i]) continue;
        if (cur.compare(t[i][0]) == 0) {
            visited[i] = true;
            answer.emplace_back(t[i][1]);
            bool isresult = dfs(t[i][1], t, usedtickets + 1);
            if (!isresult) {
                visited[i] = false;
                answer.pop_back();
            }
            else return true;
        }
    }
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    len = tickets.size();
    visited.resize(len);
    sort(tickets.begin(), tickets.end());
    fill(visited.begin(), visited.end(), false);
    answer.emplace_back("ICN");
    dfs("ICN", tickets, 0);
    for (string element : answer) {
        cout << element << ' ';
    }
    return answer;
}