[C++] 프로그래머스 lv3 여행경로 (DFS)

문제 내용

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

프로그래머스

 

풀이 내용

알파벳 순으로 경로 출력 위해 sort함

sort한 상태로 dfs 돌며 경로 찾음

경로 끝까지 갔을때(다 찾았을때)의 예외처리를 잘못해서 좀 헤맸다.. 짱ㄴㅏ..

 

사실 ICN을 첨부터 push 안하고 바로 dfs 돌면서 start를 push해도 되긴하는데

문제에서 고정값으로 준 ICN라 그냥 직역해서 풀었다

 

풀이 코드

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

using namespace std;
bool visit[10000+2];
vector<string> answer;
bool isDone;

void dfs(string start,vector<vector<string>> tickets, int cnt){
    // DFS 끝 노드까지 탐색 완료
    if(tickets.size()==cnt) {
        isDone=true;
        return;
    };
    
    for(int i=0;i<tickets.size();i++){
        if(!visit[i] && tickets[i][0].compare(start)==0) {
            string dest=tickets[i][1];
            answer.push_back(dest);
            visit[i]=true;
            dfs(dest, tickets,cnt+1);
            if(!isDone){ //DFS 탐색 다 못한채 다음 경유지 찾지 못했을때
                visit[i]=false;
                answer.pop_back();
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    
    // 알파벳 순으로 dfs 작동하도록 sort
    sort(tickets.begin(),tickets.end());
    
    // 처음은 무조건 ICN 공항 시작
    answer.push_back("ICN");
    dfs("ICN", tickets,0);

    return answer;
}