[DFS/BFS] 여행경로

yyeahh·2020년 8월 29일

프로그래머스

목록 보기

18/35

|| 문제설명 ||

주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다.
항상 ICN 공항에서 출발한다.
방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성하라.

tickets : 항공권 정보가 담긴 2차원 배열

_ 모든 공항 : 알파벳 대문자(3글자)
_ 주어진 공항 수 : 3개 이상 10,000개 이하
_ tickets의 각 행 [a, b] : a 공항에서 b 공항으로 가는 항공권
_ 주어진 항공권은 모두 사용해야 한다.
_ 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return
_ 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

|| 문제해결방법 ||

- tickets을 처음부터 정렬(첫번째는 그대로 두고 두번째들만 비교하여 재정렬) → compare 함수 수정
- 처음에는 "ICN" 미리 추가
- tickets의 첫번째 요소[0]이 "INC"이라는 확신이 없기에 DFS함수 들어가기 전에 미리 "INC"의 위치를 begin에 저장
- 정렬 된 tickets이기에 여러가지 경우를 따지지 않고 그대로 진행
- 쓴 요소는 chk == false로 만들어 건너 뛰게 만듬
- chk[i] && tickets[i][0] == tickets[begin][1]인 경우에 dfs계속 진행

|| 코드 ||

[2020.08.28] 실패

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;

bool compare(vector<string> v1, vector<string> v2) {
    return v1[0] == v2[0] && v1[1] < v2[1];
}

void dfs(int begin, vector<vector<string>> tickets, vector<bool> chk) {    
    for(int i=0; i<tickets.size(); i++) {
        if(chk[i] && tickets[i][0] == tickets[begin][1]) {
            chk[i] = false;
            answer.push_back(tickets[begin][1]);
            dfs(i, tickets, chk);
            return;
        }
    }
    answer.push_back(tickets[begin][1]);
}

vector<string> solution(vector<vector<string>> tickets) {
    int begin;
    vector<bool> chk(tickets.size(), true); 
    
    sort(tickets.begin(), tickets.end(), compare);
    for(int i=0; i<tickets.size(); i++) {
        if(tickets[i][0] == "ICN") {
            begin = i;
            chk[begin] = false;
            answer.push_back(tickets[begin][0]);
            break;
        }
    }
    dfs(begin, tickets, chk);
    
    return answer;
}

[2020.08.30] 실패

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;

void dfs(string begin, vector<vector<string>> tickets, vector<bool> chk, vector<string> ans) { 
    int c = 0;
    ans.push_back(begin);
    for(int i=0; i<tickets.size(); i++) {
        if(chk[i] && tickets[i][0] == begin) {
            c = 1;
            chk[i] = false;   
            if(tickets.size() == ans.size()) {
                ans.push_back(tickets[i][1]);
                answer = ans;
                return;
            }
            dfs(tickets[i][1], tickets, chk, ans);
            chk[i] = true;
        }
    }
    if(!c) ans.pop_back();
}

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

가능한 경로가 여러 개인 경우 알파벳 순서가 앞서는 경로를 return 해야하는데 그 외의 경우를 return

입력값 >> [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]

기댓값 >> ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

실제 return값 = { "ICN", "SFO", "ATL", "ICN", "ATL", "SFO" }

[2020.08.30] 성공

- 가장 작은 값이 나올 수 있도록 if문을 추가하여 최소값을 answer에 저장함.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;

void dfs(string begin, vector<vector<string>> tickets, vector<bool> chk, vector<string> ans) { 
    int c = 0;
    ans.push_back(begin);
    for(int i=0; i<tickets.size(); i++) {
        if(chk[i] && tickets[i][0] == begin) {
            c = 1;
            chk[i] = false;   
            if(tickets.size() == ans.size()) {
                ans.push_back(tickets[i][1]);
                if(answer.empty()) answer = ans;
                else { if(answer > ans) answer = ans;}
                return;
            }
            dfs(tickets[i][1], tickets, chk, ans);
            chk[i] = true;
        }
    }
    if(!c) ans.pop_back();
}

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

[2021.02.07]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool chk[10005];
vector<string> answer;

void dfs(string start, vector<vector<string>> tic, vector<string> tmp) {
    tmp.push_back(start);
    
    if(tmp.size() == tic.size()+1) {
        if(answer.empty()) answer = tmp;  
        return;
    }
    for(int i = 0; i < tic.size(); i++) {
        if(!chk[i] && start == tic[i][0]) {
            chk[i] = true;
            dfs(tic[i][1], tic, tmp);
            chk[i] = false;
        }
    }
}

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

- 테스트케이스 1이 너무나도 오래걸린다.
- 종료문을 추가해준다면 : 정답이 나왔을 때 더이상 검사를 하지 않도록
	(첫 번째 정답이후로는 알파벳 순서가 앞서지 않는다.)
  반복하는 경우를 제거할 수 있을 것이다.
- dfs함수를 bool형으로 바꾸어 그 값에 따라 종료 여부 결정.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool chk[10005];
vector<string> answer;

bool dfs(string start, vector<vector<string>> tic, vector<string> tmp) {
    tmp.push_back(start);
    
    if(tmp.size() == tic.size()+1) {
        if(answer.empty()) {
            answer = tmp;  
            return true;
        }
    }
    for(int i = 0; i < tic.size(); i++) {
        if(!chk[i] && start == tic[i][0]) {
            chk[i] = true;
            if(dfs(tic[i][1], tic, tmp)) return true;
            chk[i] = false;
        }
    }
    return false;
}

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