[Programmers] 여행경로

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

프로그래머스

 

1. Python

from collections import defaultdict

def solution(tickets):
    tickets.sort()
    routes = defaultdict(list)
    for u, v in tickets:
        routes[u].append(v)

    def dfs(u, tickets, path):
        if not tickets:
            return path

        for v in routes[u]:
            if [u, v] in tickets:
                tickets.remove([u, v])
                ret = dfs(v, tickets, path + [v])
                if ret is not None:
                    return ret
                tickets.append([u, v])

    return dfs("ICN", tickets, ["ICN"])

 

2. C++

vector<string> dfs(map<string, vector<string>>& routes, string u, vector<vector<string>>& tickets, vector<string> path) {
	if (tickets.empty()) return path;
	for (string v : routes[u]) {
		vector<string> tmp {u, v};
		auto it = find(tickets.begin(), tickets.end(), tmp);
		if (it != tickets.end()) {
			tickets.erase(it);
			vector<string> nxt_path {path};
			nxt_path.push_back(v);
			vector<string> ret = dfs(routes, v, tickets, nxt_path);
			if (!ret.empty()) return ret;
			tickets.push_back(tmp);
		}
	}
	return vector<string>();
}


vector<string> solution(vector<vector<string>> tickets) {
	sort(tickets.begin(), tickets.end());
	map<string, vector<string>> routes;
	for (auto ticket : tickets) {
		if (routes.find(ticket[0]) == routes.end()) {
			routes[ticket[0]] = vector<string> {ticket[1]};
		}
		else {
			routes[ticket[0]].push_back(ticket[1]);
		}
	}
	return dfs(routes, "ICN", tickets, {"ICN"});
}