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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43164

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

 

 

문제 풀이

조건을 보면 주어진 항공권은 모두 사용해야하며 가능 경로가 2개 이상일 때에는 알파벳 순서가 앞서는 경로를 return한다고 되어있다. 나는 DFS로 풀이할 것이기 때문에 visited 배열을 티켓에 대해 체크하는 용도로 사용했다.

 

우선, 알파벳 순서가 앞서는 경로를 먼저 확인하기 위해 tickets 배열을 정렬하고 "ICN"가 나오는 곳부터 DFS를 시작한다. answer에 바로 경로를 저장할 수 없으므로 임시 경로 저장 배열 tmp가 필요하다.

 

DFS를 거치며 출발지(departure)가 티켓의 출발지(tickets[i][0])와 일치하고 해당 티켓을 사용한 적 없다면 해당 티켓을 사용해서 도착지(tickets[i][1])을 다시 출발지로 설정하여 DFS를 수행한다.

 

tmp.size()가 tickets.size() + 1이 되면 모든 경로를 거친 상태이므로 DFS를 종료하게 된다. DFS 함수의 마지막 부분에는 종료할 때 임시 배열을 pop할 수 있도록 해준다. 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
vector<string> answer;
bool visited[10001] = { false, };
bool flag = false;

void DFS(vector<vector<string>> tickets, vector<string> tmp, string departure){
    if(flag) return;
    tmp.push_back(departure);
    
    if(tmp.size() == (tickets.size() + 1)){
        answer = tmp;
        flag = true;
        return;
    }
    
    for(int i=0; i<tickets.size(); i++){
        if(tickets[i][0] == departure && !visited[i]){
            visited[i] = true;
            DFS(tickets, tmp, tickets[i][1]);
            visited[i] = false;
        }
    }
    
    tmp.pop_back();
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    vector<string> tmp;
    
    DFS(tickets, tmp, "ICN");
    
    return answer;
}

 

 

시행 착오

처음에 bool 변수 flag가 없을 때에는, 분명히 sort를 했음에도 2번 테스트 케이스에서 

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"]가 나왔다.

 

무엇이 문제일까 생각해보면서 디버깅을 했는데 처음에 올바른 경로["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]가 answer에 들어가있어도 DFS를 계속해서 거치면서 나중에 찾은 경로를 answer에 다시 저장하였다.

 

따라서, 처음 경로를 찾게 되면 이미 정렬을 한 상태이므로 그 경로가 답이 되므로 flag를 이용하여 현재 돌아가고 있는 모든 DFS 함수를 종료시켜야 한다.