프로그래머스 - 여행경로(dfs)

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

프로그래머스

 

문제 풀이 과정

bfs/ dfs 풀이로 안하고, map과 vector<string>형 배열 arr을 이용하여 티켓을 순서대로 따라감 -> 1, 2번 테케 오류

arr["출발지"] = 도착지 A, 도착지 B

 

[["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]] 인 경우에서 오류가 남.

내 풀이법으로는

arr[ICN] = A

arr[A] = B, C

arr[B] = D

arr[C] = A 가 들어있다. 

 

ICN -> A -> C -> A -> B -> D 가 아닌 ICN -> A -> B -> D를 출력하게 된다. 

 

DFS 풀이법

• tickets을 알파벳 순으로 정렬
• dfs(출발지, 사용한 티켓수)로 정의
  • 모든 항공권 다 사용하면 true 
  • 항공권 다 사용못했는데 길이 없는 경우, 백트래킹

#include <bits/stdc++.h>

using namespace std;

vector<vector<string>> _tickets;
vector<string> answer;
bool vis[10002];
bool isFind;
string ans[10002];

void dfs(string st, int cnt)
{
    ans[cnt] = st;
    if(isFind) return;
    if(cnt == _tickets.size())
    {
        isFind = true;
        for(int i = 0; i <= cnt; i++)
        {
            answer.push_back(ans[i]);
        }
        return;
    }
    
    for(int i = 0; i < _tickets.size(); i++)
    {
        if(vis[i]) continue;
        if(_tickets[i][0] == st)
        {
            vis[i] = true;
            dfs(_tickets[i][1], cnt+1);
            vis[i] = false;
             
            
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    
    sort(tickets.begin(), tickets.end());
    _tickets = tickets;
    
    dfs("ICN", 0);

    return answer;
}