프로그래머스 여행경로

문제

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

코드

cpp

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

vector<int> visit(30000,0);
vector<string> ports;
vector<vector<string>> answers;

bool compare(vector<string> a,vector<string> b){
    for(int i=0;i<a.size();i++){
        if(a[i]<b[i]) return true;
        if(a[i]>b[i]) return false;
    }
}

void dfs(vector<vector<string>> tickets,string target,int d){
    if(d==tickets.size()){
        answers.push_back(ports);
        return;
    }
    
    for(int i=0;i<tickets.size();i++){
        if(visit[i]==1) continue;
        if(tickets[i][0]==target){
            ports.push_back(tickets[i][1]);
            visit[i]=1;
            dfs(tickets,tickets[i][1],d+1);
            visit[i]=0;
            ports.pop_back();
        }
    }
}
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    string start="ICN";
    ports.push_back(start);
    dfs(tickets,start, 0);
    
    sort(answers.begin(),answers.end(),compare);
    answer=answers[0];
    return answer;
}

python

from collections import defaultdict

def dfs(d,path):
    global answer
    
    if answer:
        return
    if d==n:
        answer=path
        return 
    now=path[-1]
    for i in range(len(graph[now])):
        if graph[now][i][1]:
            continue
        graph[now][i][1]=1
        next=graph[now][i][0]
        dfs(d+1,path+[next])
        graph[now][i][1]=0
    
    
def solution(tickets):
    global graph,n,answer

    answer = []
    graph=defaultdict(list)

    n=len(tickets)
    for s,e in tickets:
        graph[s].append([e,0])
        
    for key in graph:
        graph[key].sort()
    
    dfs(0,['ICN'])
    return answer

풀이

문제에서 티켓들이 주어지고 이를 전부 사용해서 "ICN"에서 모든 공항들을 거치는 경로를 만들면 됩니다 이 때 만들어지는 경로가 2개 이상이라면 공항들의 이름순으로 첫번째 경로를 배열에 담아서 출력해주면 되요

dfs 함수를 보시면 d가 티켓의 총 개수와 같아지면 모든 티켓을 다 사용했다는 뜻이니까 현재까지의 경로를 answers에 저장하고 리턴하는 재귀함수 탈출코드를 작성했습니다. 그 밑에 내용은 일반 dfs랑 비슷해서 별로 설명할게 없네요

solution함수를 보시면 문제에서 시작 공항을 'ICN'으로 고정했기 때문에 그걸 써줬고 경로가 여러개일 경우를 고려해서 비교함수를 구현하고 정렬해줬습니다.