[C++] 프로그래머스 여행경로

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

프로그래머스

풀이

모든 노드를 방문하는 경로 중 우선순위를 따지는 문제이다.

처음은 구조체를 사용해서 따로 우선순위 큐 기반의 연결 리스트 자료구조를 만들었고 스택으로 알고리즘을 구현했다. 문제는 알파벳 순 탐색을 할 때, 우선순위대로만 탐색하면 모든 공항을 돌 수 없는 경우가 있다는 것이다.

ex) 1-2/ 1-3/ 3-1 

예시의 경우 우선순위대로 1-2를 방문하지만 연결된 곳이 없어 종료하게 된다. 이러면 모든 공항을 방문해야 한다는 조건을 만족할 수 없다. 따라서 다음 우선순위인 1-3을 먼저 방문해야 한다. 이것을 체크 변수를 사용해서 체크하고, 만약 해당 경우라면 pop_back() 해주고 다음 우선순위를 push_back() 해준다.

이 부분을 놓쳤었고 문제 파악이 제대로 안된 부분이었다.

추가적으로, 따로 연결리스트를 만들 필요도 없이, 오름차순 정렬 하면 같은 출발 공항일 때 우선순위가 먼저인 도착 공항을 가지는 티켓이 앞에 오게 된다.   

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

vector<string> answer;
bool visited[100001];
bool check = false;


void dfs(string airport, vector<vector<string>> tickets,int count){
    if(count == tickets.size()){// 모두 사용
        check = true;
    } 
    answer.push_back(airport);

    for(int i=0; i<tickets.size(); i++){
        if(!visited[i] and tickets[i][0] == airport){//현재공항티켓 탐색
            visited[i] = true;
            dfs(tickets[i][1], tickets,count+1);

            if(!check){//모두 다 사용할수 없을경우
                answer.pop_back();
                visited[i] = false;
            }
        }
    }
}

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