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

programmers.co.kr/learn/courses/30/lessons/43164#

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

DFS(백트래킹)를 이용하여 해결했습니다. LEVEL 3 문제인 만큼 여러 가지 경우를 고려해야 했습니다.

처음에는 다양한 테스트 케이스를 생각하지 못하고 코드를 작성하였는데 1번과 2번 테이스 케이스에서 실패를 했습니다.

알파벳 우선순으로 방문을 해야 하기 때문에 input값인 tickets을 정렬한 상태로 DFS를 진행했습니다.

실패 소스코드 (테스트 케이스 1, 2번 실패)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> answer;

void dfs(string cur, vector<vector<string>> &tickets) {
    
    answer.push_back(cur);
    
    for (int i = 0; i < tickets.size(); i++) {
        if (tickets[i][0] == cur && tickets[i].size() == 2) {
            tickets[i].push_back("vis");
            dfs(tickets[i][1], tickets);
        }
    }
}

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

방문 체크를 하는 배열을 따로 사용하지 않고, 기존 티켓에 "vis"를 push_back 하면서 방문을 체크했습니다.

tickets[i][0] == cur && ticekts[i].size() == 2를 통해서 현재 cur에서 다음 도시로 가는 티켓이 남아 있는 경우를 확인합니다.

 

위 코드 같은 경우에는 [["BTL", "ICN"], ["ICN", "ATL], ["ICN", "BTL"]]로 정렬된 경우에 모든 도시를 방문하지 못합니다.

첫 시작이 무조건 ICN 이기 때문에 [["BTL", "ICN"], ["ICN", "ATL"], ["ICN", "BTL"]]에서 ["ICN", "BTL"] 보다 앞에 있는  ["ICN", "ATL"]을 먼저 방문하고, 다음 도시인 ATL 이 없기 때문에 answer는 ["ICN", "ATL"]인 틀린 값이 됩니다.

 

성공 소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> answer;
bool f;

void dfs(string cur, vector<vector<string>> &tickets,int cnt) {
    
    answer.push_back(cur);
    if (cnt == tickets.size()){
        f = true;
        return;
    }
    
    for (int i = 0; i < tickets.size(); i++) {
        if (tickets[i][0] == cur && tickets[i].size() == 2) {
            tickets[i].push_back("vis");
            dfs(tickets[i][1], tickets, cnt + 1);
            if (f) return;
            tickets[i].pop_back();
        }
    }
    answer.pop_back();
}

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

이 문제를 해결하기 위해서 cnt 변수와 f 변수를 통해서 지금까지 몇 개의 도시를 방문했는지, 방문이 모두 완료되었는지 확인해주며 진행합니다. 그리고 cnt == tickets.size() 모든 도시를 방문했을 때  종료시킵니다.

f 가 true이면 이전 단계의 DFS 들을 모두 종료시킬 수 있습니다.

 

그러면 [["BTL", "ICN"], ["ICN", "ATL], ["ICN", "BTL"]]와 같이 ["ICN", "ATL"]를 먼저 방문했을 때  그다음 cur = "ATL" 일 때는 for문에서 if 조건이 걸리지 않아 끝나게 됩니다.

 

그러면 ["ICN", "ATL"]를 먼저 방문하는 경우는 틀린 경우의 수가 되기 때문에 answer에서 현재 cur인 "ATL"를  pop_back() 해줍니다.

 

이렇게 cur = "ATL"인 dfs가 종료되고, f는 여전히 false입니다. ["ICN","ATL"]는 나중에 방문될 곳이기 때문에 "vis"를 pop_back() 해줍니다.

 

그럼 다시 처음으로 돌아와 이와 같은 과정을 반복하여 모든 곳을 방문할 때까지 진행하고, tickets.size() 만큼 방문하면 종료시킵니다.