[프로그래머스/고득점 Kit/깊이 너비 우선 탐색] 여행 경로

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

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

 

문제풀이

DFS / 난이도 ⭐️ / 30분

 

처음에 읽었을때 위상정렬 생각이 났지만 그래프가 순환하기 때문에 불가능하다는걸 깨달았다. 

airport별로 map에 알파벳 순으로 정렬된 vector를 저장하여 풀었다. vector를 넣을 때부터 정렬해서 넣어줬기 때문에 가장 처음 만들어진 경로가 정답이다. 

 

함정은 ["COO", "BOO"]  ["COO", "DOO"] 와 같은 상황에서 BOO 먼저가는 경우만 생각하고 DOO로 먼저가는 경로를 탐색하지 않으면 정답이 틀린다. 왜냐하면,  BOO로 먼저갈 경우 경로 자체가  완성되지 않기 때문이다.

따라서 모든 경로를 만들어보고, 경로가 완성되는지, 경로가 완성된다면 알파벳순인지를 따져야한다.

 

히든케이스

[["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]

정답

["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]

 

 

문제풀이 1) dfs + map, vector(알파벳순으로), visit배열

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

unordered_map<string, vector<string>> m;    
int answer_size;
vector<string> answer;
void dfs(string dest_airport, vector<string> &answer_v){
    if(answer_v.size() == answer_size){
        if(answer.size() == 0){
            answer.assign(answer_v.begin(), answer_v.end());    
        }
        return;
    }
    
    string str;
    for(int i=0; i<m[dest_airport].size(); i++){
        str = m[dest_airport][i];
        if(str == "")
            continue;
            
        m[dest_airport][i] = "";
        answer_v.push_back(str);
        dfs(str, answer_v);
        answer_v.pop_back();
        m[dest_airport][i] = str;
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    answer_size = tickets.size() + 1;
    
    string a,b;
    for(int i=0; i<tickets.size(); i++){
        a = tickets[i][0];
        b = tickets[i][1];
        
        if(m.find(a) != m.end())
        {
            m[a].push_back(b);
            sort(m[a].begin(), m[a].end());
        }else{
            m[a] = vector<string>();
            m[a].push_back(b);
        }
         
    }
     
    vector<string> answer_v;
    answer_v.push_back("ICN");
    dfs("ICN", answer_v);
 
    return answer;
}

 

문제풀이2) 

다른 문제풀이를 살펴보니 dfs + string, visit배열을 활용해 푼 문제도 있었다.

dfs로 모든 경로를 만들어보는데 정답을 string형태로 저장한다는게 특징이다. 모든 경로를 만들어 본 뒤, 문제 요구조건에 맞게 정답 문자열을 다시 vector형태로 변환하여 리턴한다.

 

예) 정답을 ICNJFKHND 처럼 string형태로 저장  후, 경로가 완성되면 문자열 비교를 해서 작은경우 정답을 갱신해준다. string비교 특성을 살린 풀이이다.