[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 여행경로(c++)

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

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

 

DFS를 사용해서 해결했다. 처음에는 모든 여행경로를 다 따져서 result 2차원배열에 모두 넣어두고, 그 안에서 알파벳 오름차순으로 정리하는 방법을 사용했는데, 정답 후보개수가 많아져서 답이 제대로 나오지않는듯 해서 방법을 바꿨다.

tickets에 들어있는 경로들을 제일먼저 알파벳 오름차순으로 정렬 후에 처음으로 나오는 경로를 찾아서 모든 도시를 방문 했을 경우(all_visited == true) 이면 DFS를 모두 return;으로 빠져나온 후 result를 출력했다. 

모든 도시를 방문할 수 없는 경우에는 result의 맨 뒤 경로를 계속 pop_back 시켜줬다. pop_back이 아니라 clear를 해버릴 경우에는 맨 앞의 후보가 될 수 있는 도시 ( 가지치기로 나눠질 수 있는 노드의 경우까지도) 까지 다 삭제되어버리므로 정답이 제대로 출력되지 않았다. 

---

코드(c++)

#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#define SIZE 10000

int answer = 0;
bool isVisited[SIZE];
vector<string> result;
bool no_tickets = false;
int ex = 0;
void DFS(vector<vector<string>> tickets, string start){
    
    bool all_visited = true;
    for(int v=0;v<tickets.size();v++) if(isVisited[v] != true) all_visited = false;
    if(all_visited == true) {result.push_back(start); ex = 1; return;}

    no_tickets = true;
    for(int k=0;k<tickets.size();k++)if(tickets[k][0] == start && isVisited[k] == false) no_tickets = false;

    for(int i=0;i<tickets.size() ;i++){
    
        if(tickets[i][0] == start && isVisited[i] == false ) {
            
            result.push_back(start);

            isVisited[i] = true;
            DFS(tickets, tickets[i][1]);
            if(no_tickets == true) { result.pop_back();}
            if(ex == 1) return;
            
            isVisited[i] = false;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    
    sort(tickets.begin(), tickets.end()); //티켓 알파벳 오름차순 정리
    DFS(tickets, "ICN");
    return result;
}

 

 

 

---

main포함 코드

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define SIZE 10000

int answer = 0;
bool isVisited[SIZE];
vector<string> result;
bool no_tickets = false;
int ex = 0;
void DFS(vector<vector<string>> tickets, string start){
    
    bool all_visited = true;
    for(int v=0;v<tickets.size();v++) if(isVisited[v] != true) all_visited = false;
    if(all_visited == true) {result.push_back(start); ex = 1; return;}

    no_tickets = true;
    for(int k=0;k<tickets.size();k++)if(tickets[k][0] == start && isVisited[k] == false) no_tickets = false;

    for(int i=0;i<tickets.size() ;i++){
    
        if(tickets[i][0] == start && isVisited[i] == false ) {
            
            result.push_back(start);

            isVisited[i] = true;
            DFS(tickets, tickets[i][1]);
            if(no_tickets == true) { result.pop_back();}
            if(ex == 1) return;
            
            isVisited[i] = false;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    
    sort(tickets.begin(), tickets.end()); //티켓 알파벳 오름차순 정리
    DFS(tickets, "ICN");
    return result;
}

int main(int argc, const char *argv[])
{
//    vector<vector<string>> tickets ={{"ICN", "BOO"}, {"ICN", "COO"}, {"COO", "DOO"}, {"DOO", "COO"}, {"BOO", "DOO"}, {"DOO", "BOO"}, {"BOO", "ICN"}, {"COO", "BOO"}};
    
//    vector<vector<string>> tickets = {{"ICN", "A"},{"A", "C"}, {"A", "D"}, {"D", "B"}, {"B", "A"}};
    
    vector<vector<string>> tickets = {{"ICN","B"},{"B","ICN"},{"ICN","A"},{"A","D"},{"D","A"}};
    solution(tickets);
    
    return 0;
}

 

---

사용한 테스트케이스

[["ICN", "AOO"], ["AOO", "BOO"], ["BOO", "COO"], ["COO", "DOO"], ["DOO", "EOO"], ["EOO", "DOO"], ["DOO", "COO"], ["COO", "BOO"], ["BOO", "AOO"]]     

답 ["ICN", "AOO", "BOO", "COO", "DOO", "EOO", "DOO", "COO", "BOO", "AOO"]

 

[["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]

답 ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]

 

[["ICN", "A"], ["A", "C"], ["A", "D"], ["D", "B"], ["B", "A"]]

답 ["ICN", "A", "D", "B", "A", "C"]

 

[["ICN", "B"], ["B", "ICN"], ["ICN", "A"], ["A", "D"], ["D", "A"]]

답 ["ICN", "B", "ICN", "A", "D", "A"]