[프로그래머스]깊이/너비 우선 탐색(DFS/BFS) : 여행경로 (level 3) (c++)

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

코딩테스트 연습 - 여행경로

 

dfs + 백트랙킹

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

using namespace std;

struct airport{
    string port;
    bool passed;
};

bool dfs(map<string, vector<airport>> &t_map, vector<string> &order, string now, int left)
{
    // 남은 티켓 개수가 없으면 종료
    if (left == 0)
    {
        return true;
    }

    // 현재 공항의 인접리스트 탐색 및 백트랙킹
    for (airport &to : t_map[now])
    {
        if (to.passed == false)
        {
            to.passed = true;
            order.push_back(to.port);
            // 한번이라도 모든 공항을 다 돌았다면 종료
            if (dfs(t_map, order, to.port, left - 1))
            {
                return true;
            }
            order.pop_back();
            to.passed = false;
        }
    }
    return false;
}

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

    // 오름차순 경로를 위해 ticket벡터를 오름차순 정렬
    sort(tickets.begin(), tickets.end());

    // 인접 리스트 만들기
    map<string, vector<airport>> t_map;
    for (vector<string> ticket : tickets)
    {
        t_map[ticket[0]].push_back({ ticket[1], false });
    }
    
    // 항상 ICN에서 출발
    vector<string> order;
    order.push_back("ICN");

    // dfs로 가능한 경로를 탐색하여 order벡터에 저장하기
    dfs(t_map, order, "ICN", tickets.size());

    return order;
}

 

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다.

- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

 

 

알파벳 순서로 앞서는 경로를 리턴해야 했기 때문에,

인접리스트를 만들기 전에 주어진 tickets벡터를 오름차순 정렬 하였다.

// 오름차순 경로를 위해 ticket벡터를 오름차순 정렬
sort(tickets.begin(), tickets.end());

// 인접 리스트 만들기
map<string, vector<airport>> t_map;
for (vector<string> ticket : tickets)
{
    t_map[ticket[0]].push_back({ ticket[1], false });
}

 

 

주어진 항공권을 모두 이용해야한다는 조건이 조금 특이했는데,

이는 dfs함수에서 종료조건으로 활용하면 된다. 

bool dfs(map<string, vector<airport>> &t_map, vector<string> &order, string now, int left)
{
    // 남은 티켓 개수가 없으면 종료
    if (left == 0)
    {
        return true;
    }

    // 현재 공항의 인접리스트 탐색 및 백트랙킹
    for (airport &to : t_map[now])
    {
        if (to.passed == false)
        {
            to.passed = true;
            order.push_back(to.port);
            // 한번이라도 모든 공항을 다 돌았다면 종료
            if (dfs(t_map, order, to.port, left - 1))
            {
                return true;
            }
            order.pop_back();
            to.passed = false;
        }
    }
    return false;
}

 

 

 

모든 공항은 알파벳 대문자 3글자로 이루어집니다.

위 풀이에서 위 조건은 활용하지 않았다.

dfs함수에서 경로 인자를 string으로 처리한 후, 마지막에 벡터로 파싱하라는 의도였던 것 같다.

하지만 편리성 때문에 그냥 vector로 경로를 push pop 해줬다.