프로그래머스 여행경로 // 키가 string인 dfs는 for(i)로 해결, 예외처리 백트래킹

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

프로그래머스

* 문제1 : 알파벳순서대로 방문

해결 : dfs전 정렬

 

*문제2 : 키가 string인데? visit[string]가능? ㄴㄴ

해결 : 원소가 2개밖에없으므로 for(i)로 돌면서 2차원벡터 방문 여부만 체크.

접근은 ticket[i][0], [i][1]로 접근

 

*문제 3: a->b c->d 인거는 못가고, a->b, b->c 인거만 가야함

해결 : 이전값(b)과 현재값(c)이 다르면 pass

구현 : 매개변수에 이전값인 here 저장.

if(ticket[i][0] != here) continue;

 

*문제4: 알파벳순정렬 => 티켓못쓰는 경우가 생김. 티켓을다써야함

검은색경로가 생김.

해결 : X친 노드를 pop하고 돌아가서 다시 탐색해야함.

구현 : size체크, pop,노방문처리

if(count==ticket.size()){
        fin=true;
    }

 if(!fin){
            answer.pop_back();
            visited[i]=0;
        }

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
vector<string> answer;
int visited[10004];
vector<vector<string>> ticket;
bool fin;

void dfs(string here, int count){
    //visited[here]=1;
    if(count==ticket.size()){
        fin=true;
    }
    
    for(int i=0;i<ticket.size();++i){
        if(visited[i]) continue;
        string there="";
        there=ticket[i][1];
        if(ticket[i][0] != here) continue;
        
        answer.push_back(there);
        visited[i]=1;
        dfs(there,count+1);
        
        if(!fin){
            answer.pop_back();
            visited[i]=0;
        }
    }
    return;
}

//2차원벡터를 2차원배열로 생각하라.
vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(),tickets.end());    //알파벳순서
    ticket=tickets; //자유롭게사용위해
    answer.push_back("ICN");
    dfs("ICN",0);
    return answer;
}