[프로그래머스 LV3] - 여행경로(dfs) c++

문제

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

프로그래머스

접근방법

dfs로 풀 수 있었다.

 

가장 고민했던 부분은

알파벳 순서가 낮은 경로를 통해야만

전 경로를 돌 수 있는 경우였다.

 

이것을 어떻게 처리해야할 지 감이 안잡혔다.

 

dfs로 하면 될 거 같긴한데, 자꾸 에러가 나서 gpt에게 여쭤봤다.

 

코드가 간결하고 명확햇다.

 

dfs를 돌면서

원소를 pop해버리면 경로가 온전히 저장되지 않을 거라고 생각했는데,

dfs에 대한 오해가 있었다.

 

어차피 모든 도시를 방문할 수 없는 경우는 주어지지 않으므로

dfs를 이용했을 때, 

 

먼저 출발한 루트가 순환이 없이 끝난다면

그것이 정답이 될 것이고,

 

순환이 없지만, 스택에 남은 원소가 있다면

그 원소를 통해 가는 루트는 반드시 순환이 있어야한다.

 

만약 처음 출발한 루트에서 순환이 생긴다면,

스택에 남은 원소를 통해 가는 루트는 순환이 없을 수 있다.

 

코드

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

using namespace std;

// DFS 함수 정의
void dfs(string airport, map<string, vector<string>>& graph, vector<string>& answer) {
    while (!graph[airport].empty()) {
        string next = graph[airport].back(); // 다음 공항 선택
        graph[airport].pop_back(); // 선택한 항공권 제거
        dfs(next, graph, answer); // 다음 공항으로 이동
    }
    answer.push_back(airport); // 경로에 현재 공항 추가
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;

    map<string, vector<string>> graph;

    
    // 그래프 생성
    for (auto ticket : tickets) {
        graph[ticket[0]].push_back(ticket[1]);
    }

    // 알파벳 역순으로 정렬하여 뒤에서부터 탐색하면 알파벳 순서가 앞서는 경로를 찾을 수 있음
    for (auto& g : graph) {
        sort(g.second.begin(), g.second.end(), greater<string>());
    }

    dfs("ICN", graph, answer);

    // DFS로 구한 경로는 역순으로 저장되어 있으므로 뒤집어줌
    reverse(answer.begin(), answer.end());

    return answer;
}

개선할 점

dfs에 대한 이해 부족. 문제 이해 부족이었다.

 

스택은 원소가 들어갈 때마다 한개 씩 pop하는 거지,

모든 원소를 집어넣고

그제서야 pop하는 것이 아니다.

 

문제를 보고 dfs임을 이해했다면,

도식을 그려서 풀이가 어떻게 진행되는 지 살펴봤다면 좋았을 거 같다.