[프로그래머스 43164] - 여행경로

문제 출처

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

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

 

문제 풀이

dfs로 풀이했는데 전체 탐색을 중간에 멈추는 방법을 생각하지 못했다. 그래서 탐색할 수 있는 전체 경로가 출력되서 자꾸 테스트 케이스도 통과 못하는 경우가 발생했다.
생각한 해결책은 2차원 벡터를 만들어 기저조건일 때 2차원 벡터에 경로를 넣어주는 것이다. 이후 전체 탐색이 완료되면 정렬한뒤 가장 앞에 있는 경로를 return하면 된다.
dfs탐색은 보통 알고 있는 방법대로 진행했는데 탈출 조건이나 정답을 return하는게 더 어려웠던 문제.

 

 

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C.cpp

sw93/algorithm

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<bool> visit;
vector<string> path;
vector<vector<string>> answer;
void getTravelPath(vector<vector<string>> &tickets, string from, int depth) {
	if (tickets.size() == depth) {
		answer.push_back(path);
		return;
	}

	for (int i=0; i<tickets.size(); i++) {
		if (visit[i] || from != tickets[i][0]) continue;
		visit[i] = 1;
		path.push_back(tickets[i][1]);
		getTravelPath(tickets, tickets[i][1], depth+1);
		path.pop_back();
		visit[i] = 0;
	}
}
vector<string> solution(vector<vector<string>> tickets) {
    visit.resize(tickets.size(), 0);
    path.push_back("ICN");
    getTravelPath(tickets, "ICN", 0);
    sort(answer.begin(), answer.end());
    return answer.front();
}