(프로그래머스 c++)여행경로

DFS 문제.

전역변수로 bool형 visited[10001]을 선언하여 false로 초기화.

마찬가지로 vector<string> answer, int max_count = 0으로 선언하여 사용하기 쉽게 만든다.

 

우선 sort를 수행한다.

가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 선택하기 편하도록 하기 위함이다.

그리고 임시변수 tmp를 선언하고, dfs 함수에 전달.

처음에는 "ICN"에서 출발하기 때문에 dfs(tickets, tmp, "ICN", 0)으로 호출한다.

 

dfs함수를 재귀적으로 호출.

for문을 돌면서 start와 같으면서 방문하지 않았다면

visited[i] = true로 바꿔주고, dfs 함수에 다음 목적지를 전달하도록 해주면 알아서 재귀적으로 답을 찾아준다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
bool visited[10001] = {false, };
vector<string> answer;
int max_count = 0;

void dfs(vector<vector<string>> tickets, vector<string> tmp, string start, int count)
{
    tmp.push_back(start);
    
    if(max_count < count)
    {
        max_count = count;
        answer = tmp;
    }
    
    for(int i = 0; i < tickets.size(); i++)
    {
        if(tickets[i][0] == start && visited[i] == false)
        {
            visited[i] = true;
            dfs(tickets, tmp, tickets[i][1], count + 1);
            visited[i] = false;
        }
    }
    tmp.pop_back();
}

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