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

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

코딩테스트 연습 - 여행경로

 

풀이

DFS

• tickets을 정렬한다 (가능한 경로가 2개 이상일 경우 알파벳 순서로 반환해야 하므로)
• ICN을 시작으로 dfs 탐색한다.
• dfs 함수는 현재 공항을 인자로 받아, 현재 공항을 방문처리하고 도착지에 대해 다시 dfs를 호출한다.
• 여기서 주의해야 할 것은 길이 끊어진 경우를 처리해줘야 한다는 것이다. 
  • [["ICN", "JFK"], ["ICN", "IAD"], ["JFK", "ICN"]] 와 같은 경우.
• dfs 탐색이 끝났을 때 모든 도시를 방문하지 않은 경우, answer에서 해당 도시를 빼고 방문처리를 삭제한다.

 

 

소스코드

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

vector<string> answer;
bool visited[100000001];
bool flag = false;
int cnt = 0;

void dfs(string cur, vector<vector<string>> tickets){
    if(cnt == (int)tickets.size()) flag = true;
    answer.push_back(cur);
    for(unsigned int i=0; i<tickets.size(); i++){
        if(!visited[i] && tickets[i][0] == cur){
            visited[i] = true;
            cnt++;
            dfs(tickets[i][1], tickets);

            //길이 끊긴 경우 backtrack
            if(!flag){
                answer.pop_back();
                visited[i] = false;
            }
        }
    }
}

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

 

🤐 사족

계속 테케 1, 2번이 틀리길래, 알아보니 그래프 연결이 끊긴 경우를 생각하지 않아서 그렇다고 한다. 근데 이것도 문제지만 처음에 구조 자체를 너무 복잡하게 생각했다. DFS를 Linked-List로 구현할 때 무조건 int로 접근해야 한다고 생각했고, 정렬도 그냥 애초에 정렬하고 시작하면 될텐데 뻘짓했다. 처음부터 완전 잘못 생각했다는 걸 깨닫고 싹 갈아엎어 지금 코드가 나왔다.

 

 

Reference

• https://nanyoungkim.tistory.com/93