lv3) 여행경로 (BFS로 풀어보기)

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

프로그래머스

 

https://leetcode.com/problems/reconstruct-itinerary/description/

 

 

DFS

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;
vector<bool>visited;
bool dfs(string frontW, const vector<vector<string>> tickets, vector<string>& ans, int lv){ //vector<string> ans는 call by value로 call by ref를 적용 목적 & 표시
    if(lv == tickets.size()){ // 0으로 시작하는 lv이 tickets.size() 즉 크기가 tickets.size() +1 까지 만들기.  
       return true; 
    }
    for(int idx = 0; idx < tickets.size();++idx){
        if(visited[idx] == false && tickets[idx][0] == frontW){
            visited[idx] = true;
            ans.push_back(tickets[idx][1]);
            bool rt = dfs(tickets[idx][1], tickets, ans, lv+1);
            if(rt==true) return true;
            ans.pop_back();
            visited[idx]=false;
        }
    }
    return false;
}
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end());// 2차원 첫번째 원소와 두번째 원소 오름차순정렬
    for(int idx = 0; idx < tickets.size();++idx){
        visited.push_back(false);
    }
    answer.push_back("ICN");
    bool rt = dfs(answer[0], tickets, answer, 0);
    return answer;
}

 

DFS(완전탐색 통한 모든 경우 중 문제에 나오는 조건 찾기)가 BFS(최단 경로 찾는 목적)보단 효율적.

 

BFS (TODO)