아니 나는 이런 것도 못푸나...

DFS, BFS는 이제 껌이지. 하는 생각을 하면서 살다가 이 문제를 마주하였다. 어려웠다. 다른 사람의 코드를 봐도 어려웠다. 이제 풀기는 했는데 나는 인간이고, 인간은 망각하는 동물인데 나는 인간성이 뛰어난 사람이니까 적어놓는다.

문제는 여기에

나의 풀이

  • 먼저 tickets 벡터를 순회하면서 unordered_map에 집어넣었다. key는 ticket의 출발지로 하고, value는 목적지 string의 list로 하여 일종의 연결리스트로 구현된 그래프 형태로 초기화 하였다. 초기화 한 후 알파벳 순으로 앞선 경로를 출력하기 위해 map을 순회하면서 value를 사전 순으로 정렬하였다. 다음과 같은 식으로.

  • 예제 #1
    슬라이드1.PNG

  • 예제 #2
    슬라이드2.PNG

  • 이런 식으로 초기화 한 후 일종의 DFS를 구현해 문제를 풀었다. 재귀함수를 이용하였다. 재귀함수 trip은 다음과 같이 구현하였다.

  • 먼저 from에서 출발하여 더 갈 수 있는 곳이 있는지 확인한다.

    • 없다면 경로가 만들어졌는지 확인한다. 지금까지 썼던 티켓의 갯수를 기록한 count변수를 확인한다.
      • count가 총 티켓의 갯수와 같다면 경로가 잘 만들어 졌으니 true를 반환한다.
      • count가 총 티켓의 갯수보다 작다면 아직 써야 하는 티켓이 남았는데 더이상 이동 할 수 없으니 현재 경로가 잘못된 것이다. false를 반환한다.
    • 있다면 이제 map에서 from을 key로 하는 value를 찾아서 순회한다.
      순회하면서 일단 목적지를 답안 벡터에 추가하고, count변수에 1을 더한다. 그리고 현재 출발지의 목적지 목록에서 현재 목적지를 제거한다.
      그리고 삭제한 목적지를 출발지로 하여 다시 trip함수를 호출한다.
      trip 함수가 반환하는 값을 확인한다.
      • 값이 false이면
        이 경로는 문제가 있다.
        count, 목적지 목록, 답안 벡터를 원상태로 돌리고 false를 반환한다.
      • 값이 true이면
        이 경로는 문제가 없다. true를 반환한다.
  • solution함수에서 초기화가 끝난 후 "ICN"을 시작으로 하여 trip함수를 호출해 주면 된다.

코드

#include <vector>
#include <unordered_map>
#include <string>
#include <list>
using namespace std;

bool trip(
    const int ticketNumber,
    unordered_map<string, list<string>>& mp,
    string from,
    int count,
    vector<string>& answer
) {
    list<string>& current = mp[from];
    if (current.size() == 0) {    //여기선 더 갈 데가 없어...
        if (count == ticketNumber) {    //그런데 티켓도 다썼어.
            return true;    //경로가 만들어 졌음을 알리자.
        }
        else {    //티켓이 남았는데 이동할 곳이 없어.
            return false; //이 길이 아니라는 것을 알리자.
        }
    }
    else {    //아직 이 공항에서 출발할 수 있는 티켓이 남았어!
        for (auto iter = current.begin(); 
            iter!=current.end(); 
            iter++) 
        {
            string to = *iter;    //목적지를 설정합니다.
            auto iiter = iter;    //이 길이 아닌 경우를 대비해
                //다음 경로의 iterator를 저장합니다.
            iiter++;    //다음 경로의 iterator입니다.
            current.erase(iter);    
                //티켓을 사용했으니 목적지 목록에서 지워줍니다.
            count++;
                //사용한 티겟 갯수를 1 증가합니다.
            answer.push_back(to);    //일단 답안에도 추가합니다.
            bool result = trip(
                ticketNumber,
                mp,
                to,
                count,
                answer);    //목적지로 여행하고 결과를 받아옵니다.
            if (result == true) {
                //경로가 만들어졌나 봅니다.
                //어서 알려줍시다.
                return true;
            }
            else {    //이 길이 아닌가 봅니다.
                //티켓 사용을 취소하고 다시 목록에 넣어줍니다.
                iter = current.insert(iiter, to);    
                    //순서에 맞게 목적지를 추가하였습니다.
                count--;    //사용한 티켓 갯수도 줄입니다.
                answer.pop_back();    //답안에서도 지웁니다.
            }
        }
        //다 돌았는데 아직 결과가 없다면 이길은 아닌가 봅니다.
        //아니라는 사실을 알려줍니다.
        return false;    //이 길이 아니에요...
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;

    unordered_map<string, list<string>> mp;    
    //공항 간 관계 그래프
    const string start = "ICN";
    const int ticketNumber = tickets.size();

    for (int i = 0; i < tickets.size(); i++) {    //티켓들 순회
        string from = tickets[i][0];    //출발 공항
        string to = tickets[i][1];    //도착 공항
        mp[from].push_back(to);    
        //각 출발 공항에 대한 도착공항 배열에 공항 추가
    }
    for (auto iter = mp.begin(); iter != mp.end(); iter++) {
        //각 출발 공항에 대하여 도착 공항 정렬
        (iter->second).sort();
    }

    answer.push_back(start);
    trip(ticketNumber, mp, start, 0, answer);
    return answer;
}

그러니까

다른 이들의 코드와 설명을 10개 정도 보고서야 대충 이해를 했다. 심지어 다들 나보다 간단하게 풀었던데 그 풀이들은 이해를 못했다... 나는 아직 많이 멀었구나.