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

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

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

using namespace std;
bool visited[100000001];
vector<string>answer;
vector<vector<string>>temp;
void dfs(vector<vector<string>>&tickets,int idx){//idx번 티켓사용
   if(answer.size()==tickets.size()){ //기저
       answer.push_back(tickets[idx][1]);
       temp.push_back(answer);
   }else{
    string from=tickets[idx][1]; //출발지
    answer.push_back(from);
    for(int i=0;i<tickets.size();i++){
        if(visited[i])continue; //이미 사용했다면 continue
        else if(!visited[i] && tickets[i][0]==from){//사용하지 않았다면
            visited[i]=true;
            dfs(tickets,i);
        }
    }
   }
    answer.pop_back();
    visited[idx]=false;
}
vector<string> solution(vector<vector<string>> tickets) {
    memset(visited,false,sizeof(visited));
    for(int i=0;i<tickets.size();i++){
        if(tickets[i][0]=="ICN"){
            visited[i]=true;
            answer.push_back("ICN");
            dfs(tickets,i);  //ICN출발 티켓마다 DFS
            answer.pop_back();
            visited[i]=false;
        }
    }
    sort(temp.begin(),temp.end());
    return temp[0];
}

programmers 연습문제 level 3 dfs/bfs 문제입니다.

모든 티켓을 사용하는게 이 문제의 핵심입니다.

최단거리를 찾는데 좋은 BFS보다는

깊고 모든경우를 살피기 좋은 DFS를 사용했습니다.

 

DFS한 깊이를 내려갈때마다 visited에 체크를 해주고, DFS에서 return할때 방금 방문한 visited를 다시 false로 바꾸어줍니다.

여러 방법으로도 모든 티켓을 소진할 수 있으므로, 길을 잘못들었을때, 그리고 길을 찾은 뒤에 다시 미방문처리를 해주어야 모든 방법을 탐색할 수 있습니다.

 

길을 찾았을때 temp에 저장하고, sort를 통해 사전순으로 가장빠른 답을 출력합니다.