[프로그래머스] DFS/백트래킹 여행경로

문제 링크

접근 방식

공항은 Vertex 이고, 티켓은 두 정점을 잇는 단방향 정보인 Edge 라서 해당 문제는 그래프 탐색 문제일 가능성이 높다. 그래프 탐색이라면 BFS 또는 DFS로 접근할 수 있고, 문제에서 요구하는 답은 ICN 공항에서 출발하여 경로를 거친 순서대로 출력하는 것이므로 오직 한 가지의 경로에 대해서만 중점을 맞추는 DFS로 접근해보았다.

DFS를 구현할 때는, 탐색 함수 매개변수와 종료 조건이 중요하다.

탐색 목표: 목적지, 몇번째 방문인지.
탐색 종료 조건: 티켓 개수가 방문 순서와 똑같으면 모든 티켓을 사용한 것이므로 종료한다.

코드

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

vector<string> answer;
vector<vector<string>> input_tickets;
vector<bool> visited;

void dfs(string start, vector<string>& path, int cnt)
{
	path.push_back(start); // 현재 위치를 경로에 추가

	// 모든 항공권을 사용했을 경우
	if (cnt == input_tickets.size())
	{
		answer = path; // 정답을 현재 경로로 설정
		return;
	}

	// 모든 항공권을 사용하지 않았을 경우
	for (int i = 0; i < input_tickets.size(); i++)
	{
    	// 사용하지 않은 항공권이고, 현재 항공권의 도착 공항과 사용하려는 항공권의 시작 공항이 같으면 dfs 수행
		if (input_tickets[i][0] == start && !visited[i]) 
		{
			visited[i] = true;
			dfs(input_tickets[i][1], path, cnt + 1);
			visited[i] = false; // 백트래킹 원상복구 : 다른 경로로의 탐색을 위해 (항공권을 다시 사용할 수 있도록) 사용했던 항공권 정보를 초기화한다
			if (!answer.empty()) return; // 정답을 찾으면 더 이상 진행하지 않는다
		}
	}
	path.pop_back(); // 현재 위치를 경로에서 제거 (백트래킹)
}

vector<string> solution(vector<vector<string>> tickets)
{
	input_tickets = tickets;
	visited.resize(input_tickets.size(), false);
	sort(input_tickets.begin(), input_tickets.end()); // 알파벳 순 정렬
	vector<string> path; // 현재 경로를 저장할 벡터
	dfs("ICN", path, 0);
	return answer;
}