여행경로 C++(dfs/bfs)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 여행경로 | 프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 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" }

 

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

---

2. 문제풀이

#삽질했던 내용

1. 처음에 ICN인지 확인하기위해 2중포문으로 작성하였었다. 그로인해 비슷한 비교코드가 생성되어 함수를 2개로 분리했다. 1번함수에서 2번함수로넘어가 비교하고 조건이 맞다면 다시 1번함수로 재귀하는 형식이었다. 코드도 길어졌고 알파벳순으로 경로를 찾지못하였다.   2. 알파벳순으로 찾기위해 정답리스트를 따로만들어서 정답이 들어갈 경우의 수를 넣었다. 반환직전에 정렬을하고 알파벳순으로 제일 빠른 경로를 반환하였다. 처음에 ICN으로 출발해야하는데 ATL에서 출발하는 특이한 경우가 발생하였다.   3. 정답리스트에 넣는과정에서 주소전달을 이용하였는데 원본을 정렬한 상태로 사용을해서 문제가 생겼던 것이었다. 임시 리스트를 만들어서 정렬후 사용하였더니 문제가 해결되었다.

# 최종문제풀이

삽질로 인해 생각보다 시간을 많이썻던 문제였습니다. 정리하고 보니 결거없었는데 말이죠... 하나씩 접근해보겠습니다.   1. 모든 항공권을 사용해야합니다. 따라서 어떠한 항공권을 사용했는지 체크를 해야합니다. 2. 가능한 경로가 2개이상일 경우 알파벳 순서가 앞서는 경로를 return합니다. 따라서 경로를 찾으면 멈추는 것이 아니라 다른 경로 또한 찾아야 합니다. 경로를 찾았다면 정렬을해서 값을 반환합니다.   그렇다면 탐색문제이기 때문에 함수를 하나만들어줍니다. tickets는 전역변수로 선언해도 상관없지만 저는 넣었습니다. tickets에서 어떤 항공권을 사용했는지 체크하기 위해서 useCheck라는 변수를 만들었습니다. 형태는 vector<pair<int, int>>형태이며 앞에가 사용한 순서이고 뒤에가 tickets의 index입니다. 순서대로 정렬했을때 index로 편하게 접근하기 위해 pair를 이용했습니다. 원상태로 정렬을하고 다른경로를 찾게되면 위치가 바뀌었기때문에 결과가 꼬이게됩니다. 임시변수를 만들어서 정렬을 하도록 합니다. 함수를 나오게되면 그전에 사용한 항공권은 사용하지 않은것으로 변경해줘야 합니다. 그래야 다음반복문에서 사용을 할 수 있기 때문입니다.   출발지를 명시하기 위해 어디서 출발하는지 from변수를 포함했습니다. 처음에 시작할때 "ICN"으로 넣고 시작합니다. 그러면 출발지가 ICN인 곳을 찾아서 탐색을 시작합니다. 일치한다면 도착지를 from쪽에 넣어서 다시 재귀시킵니다.   티켓을 사용한 횟수를 파악하기위해 count변수를 포함했습니다. depth로 만들어도 상관없습니다. 함수를 재귀할때마다 한개씩 증가시킵니다.   만약 count변수가 tickets의 size와 같아진는걸 return조건으로 만들고 여기까지 왔다면 모든 항공권을 다사용한 것이므로 정답 리스트에 추가하는  코드도 넣어줍니다.   모든 경로의 탐색이 끝났다면 정답리스트를 정렬하고 가장 알파벳순이 빠른 경로를 반환합니다.   말로 쓰니까 생각보다 복잡해지네요. 프로그래머는 코드로 대화합니다! 이해를 못하시겠다면 코드를 보며 확인해보세요.

 

---

3. 소스코드

3.1 주석없는 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<string>> answerlist;
 
void dfs(vector<vector<string>>& tickets, vector<pair<int, int>>& useCheck, string from, int count) {
    if (count == tickets.size()) {
        vector<string> answer;
        vector<pair<int, int>> temp = useCheck;
        sort(temp.begin(), temp.end());
        for (auto a : temp)        answer.push_back(tickets[a.second][0]);
        answer.push_back(tickets[temp[temp.size() - 1].second][1]);
        answerlist.push_back(answer);
        return;
    }
    for (int i = 0; i < tickets.size(); i++) {
        if (useCheck[i].second == -1 && tickets[i][0] == from) {
            useCheck[i] = { count, i };
            dfs(tickets, useCheck, tickets[i][1], count + 1);
            useCheck[i] = { 0, -1 };
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    vector<pair<int, int>> useCheck(tickets.size(), { 0 , -1 });
    dfs(tickets, useCheck, "ICN", 0);
    sort(answerlist.begin(), answerlist.end());
    return answerlist[0];
}

3.2 주석있는 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<vector<string>> answerlist;
 
void dfs(vector<vector<string>>& tickets, vector<pair<int, int>>& useCheck, string from, int count) {
    //리턴조건 티켓을 모두다 사용했다면
    if (count == tickets.size()) {
        //정답후보 생성
        vector<string> answer;
        //기존 내용이 바뀌면 안되기때문에 임시로 하나 생성 후 정렬
        vector<pair<int, int>> temp = useCheck;
        sort(temp.begin(), temp.end());
        //순서대로 정답에추가
        for (auto a : temp)        answer.push_back(tickets[a.second][0]);
        //마지막 행성지는 따로 추가해줌
        answer.push_back(tickets[temp[temp.size() - 1].second][1]);
        //정답리스트에 추가하고 리턴
        answerlist.push_back(answer);
        return;
    }
    for (int i = 0; i < tickets.size(); i++) {
        //사용을 안한티켓이고 행선지가 같을때
        if (useCheck[i].second == -1 && tickets[i][0] == from) {
            //사용했다고 변경하고
            useCheck[i] = { count, i };
            //재귀함
            dfs(tickets, useCheck, tickets[i][1], count + 1);
            //사용을 다했으면 사용했다는 내용 삭제
            useCheck[i] = { 0, -1 };
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    //사용여부를 관리할 임시변수 (순서, 인덱스번호)
    vector<pair<int, int>> useCheck(tickets.size(), { 0 , -1 });
    //처음은 ICN에서 출발해야 한다.
    dfs(tickets, useCheck, "ICN", 0);
    //알파벳 순으로 반환해야 하기때문에 정렬
    sort(answerlist.begin(), answerlist.end());
    //제일 앞에있는것이 알파벳 순으로 정렬된 것이다.
    return answerlist[0];
}

3.3 테스트 코드 추가

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
vector<vector<string>> answerlist;
 
void dfs(vector<vector<string>>& tickets, vector<pair<int, int>>& useCheck, string from, int count) {
    //리턴조건 티켓을 모두다 사용했다면
    if (count == tickets.size()) {
        //정답후보 생성
        vector<string> answer;
        //기존 내용이 바뀌면 안되기때문에 임시로 하나 생성 후 정렬
        vector<pair<int, int>> temp = useCheck;
        sort(temp.begin(), temp.end());
        //순서대로 정답에추가
        for (auto a : temp)        answer.push_back(tickets[a.second][0]);
        //마지막 행성지는 따로 추가해줌
        answer.push_back(tickets[temp[temp.size() - 1].second][1]);
        //정답리스트에 추가하고 리턴
        answerlist.push_back(answer);
        return;
    }
    for (int i = 0; i < tickets.size(); i++) {
        //사용을 안한티켓이고 행선지가 같을때
        if (useCheck[i].second == -1 && tickets[i][0] == from) {
            //사용했다고 변경하고
            useCheck[i] = { count, i };
            //재귀함
            dfs(tickets, useCheck, tickets[i][1], count + 1);
            //사용을 다했으면 사용했다는 내용 삭제
            useCheck[i] = { 0, -1 };
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    //사용여부를 관리할 임시변수 (순서, 인덱스번호)
    vector<pair<int, int>> useCheck(tickets.size(), { 0 , -1 });
    //처음은 ICN에서 출발해야 한다.
    dfs(tickets, useCheck, "ICN", 0);
    //알파벳 순으로 반환해야 하기때문에 정렬
    sort(answerlist.begin(), answerlist.end());
    //제일 앞에있는것이 알파벳 순으로 정렬된 것이다.
    return answerlist[0];
}
 
void print(vector<vector<string>> tickets, vector<string> answer) {
    vector<string> t = solution(tickets);
    if (t == answer)        cout << "정답" << endl;
    else        cout << "틀림" << endl;
    answerlist.clear();
}
 
int main() {
    print({ {"ICN","JFK"}, {"HND", "IAD"}, {"JFK", "HND"} }, { "ICN", "JFK", "HND", "IAD" });
    print({ {"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"} }, { "ICN", "ATL", "ICN", "SFO", "ATL", "SFO" });
    return 0;
}

---

4. 결과