DFS/BFS 여행 경로

<문제>

프로그래머스 DFS/BFS 3단계 문제.

<문제 풀이>

문제 해결을 위해 적용한 규칙

 

1.경로의 수는 항상 tickets배열의  원소 수보다 1 더 많다. 

2.여행 경로는 도착 여행지(두번째 인자)가  출발 여행지(첫번째 인자)와 같을 때 이어진다.

3.한번 방문한 도시는 방문하지 않는다. 

4.만약 출발할 수 있는 경로가 2개라면 도착 여행지의 이름이 알파벳 순으로 더 빠른 도시를 택한다.

 

1번 조건은 DFS를 종료하는 조건이 된다.

- idx가 tickets.size+1 과 같을 때 해당 일을 수행하고 종료.

 

2번 조건은 DFS에서 다음 여행 경로를 선택하는 조건이 된다.

- '현재 여행지' 와 '(3번 조건=방문하지 않았던) tickets배열의 첫번째 인자' 를 비교하여 같으면 여행지를 바꾼다.

 

4번 조건을 만족시키기 위해서는

 

1.dfs의 for문 마다 가장 알파벳이 앞선걸 찾아서 대입한 다음 가느냐.

2.dfs 종료 단계에서 여행 경로가 완성된 배열들끼리 비교하여 가장 알파벳 순서가 빠른 배열만 남기느냐

 

1번을 하기에는 더 번거로워서 

(->for문마다 모든 tickets리스트를 돌면서 비교를 해야하고, 비교한다음에는 몇번째 가장 빠른 원소의 인덱스까지 기억해서 visited배열에도 해당 인덱스를 TRUE로 만들어야 하기 때문에.)

 

2번 방법을

    if(idx == tickets.size()) {
        if(answer[1] == "")  
            copy(answer, result);

        else {
            //즉 아스키 숫자가 더 작은 쪽이 선택된다.
            //answer가 더 알파벳 순서가 앞서면 true. 그렇지 않으면 false
            if(compare(answer, result)) return;
            else copy(answer, result);
        }
        
        return;
    }
    

이런식으로 1,2,3번 조건을 만족시킨 모든 여행 경로가 result에 담겨오면 answer(이전 result값)와 result를 알파벳 순서가 빠른지 비교하여 빠른 것이 answer에 담기도록(copy) 구현하였다.

 

 

<코드 구현>

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

vector<bool> visited;
vector<string> result;

void dfs(vector<vector<string>>, vector<string>&, string, int);
bool compare(vector<string>, vector<string>);
void copy(vector<string>&, vector<string>);

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer(tickets.size()+1, "");
    visited = vector<bool>(tickets.size(), false);
    
    answer[0] = "ICN";
    result.push_back("ICN");
    
    dfs(tickets, answer, "ICN", 0);
    
    return answer;
}


void dfs(vector<vector<string>> tickets, vector<string>& answer, string ticket, int idx){
    if(idx == tickets.size()) {
        if(answer[1] == "")  
            copy(answer, result);

        else {
            //즉 아스키 숫자가 더 작은 쪽이 선택된다.
            //answer가 더 알파벳 순서가 앞서면 true. 그렇지 않으면 false
            if(compare(answer, result)) return;
            else copy(answer, result);
        }
        
        return;
    }
    
    for(int i=0; i<tickets.size();++i) {
        if(visited[i] || tickets[i][0] != ticket) continue;
        string tmp; tmp = ticket;
        
        visited[i] = true;
        ticket = tickets[i][1];
        result.push_back(ticket);
        
        dfs(tickets,answer,ticket,idx+1);
        
        visited[i] = false;
        ticket = tmp;
        result.pop_back();
    } 
    
    return;
}

bool compare(vector<string> a, vector<string> b) {
    for(int i=0; i<a.size(); ++i) {
        if(a[i] == b[i]) continue;
        if(a[i] < b[i]) return true;
        else return false;
    }
    
    return true;
        
}

void copy(vector<string>& a, vector<string> b) {
     for(int i=0; i<a.size(); ++i) 
        a[i] = b[i];
}