C++ / 프로그래머스 / 여행경로

문제

 

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

프로그래머스

문제풀이

 

DFS로 풀었다. DFS는 시작 나라, 여행 횟수, 여행경로를 인자로 받았다.

visited 벡터를 이용해 재방문을 못하게 했다.

반복문을 탐색하면서 출발지점이 "ICN"이라면 방문 표시를 하고, 여행경로에 string형으로 입력한다.

 

DFS함수에서는 티켓 크기만큼 반복하면서 티켓을 탐색한다.

방문을 안 했고, 현재 나라가 출발 지점이 아닌 티켓들은 continue를 통해 넘긴다.

다음으로 갈 나라가 마지막 나라라면 answer을 최솟값으로 바꾼다.

그렇지 않다면 도착 나라, 횟수 +1, 현재 나라를 입력하여 DFS함수를 실행한다.

 

DFS함수가 모두 끝났으면, istringstream을 통해 띄어쓰기 단위로 문자열을 파싱 하여 answer_v 벡터에 저장한다.

 

코드

#include <string>
#include <vector>
#include <sstream>
using namespace std;
vector<bool>visited;
vector<vector<string>>ticket;
string answer("Z");
void DFS(string start, int cnt, string route) {
    int idx(0);

    for (idx = 0; idx < ticket.size(); ++idx) {
        if (visited[idx] == false) {
            if (start != ticket[idx][0]) continue;
            if (cnt + 1 == ticket.size()) {
                answer = min(answer, route + " " + ticket[idx][1]);
            }
            else {
                visited[idx] = true;
                DFS(ticket[idx][1], cnt + 1, route + " " + ticket[idx][1]);
                visited[idx] = false;
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    string country("");
    ticket = tickets;
    visited = vector<bool>(tickets.size(), false);
    vector<string>answer_v;
    int idx(0);
    string route("");

    route = "ICN ";
    for (idx = 0; idx < ticket.size(); ++idx) {
        if (tickets[idx][0] == "ICN") {
            visited[idx] = true;
            DFS(tickets[idx][1], 1, route + tickets[idx][1]);
            visited[idx] = false;
        }
    }

    istringstream iss(answer);

    while (getline(iss, country, ' ')) {
        answer_v.push_back(country);
    }

    return answer_v;
}