[프로그래머스] DFS 여행경로 (C++ / Python3)

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

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

 

[풀이방법]

c++/ python 둘다 같은 로직으로 풀었습니다.

1. 주어진 tickets 을 알파벳 순으로 정렬한다.

2. 첫 시작공항인 ICN을 start 로 설정한 후 dfs 탐색을 시작한다.

3. start를 첫번째 인자로 하는 티켓을 탐색한다. 

4. 해당 티켓의 두번째인자는 목적지이므로 두번째 인자를 start 로 설정하고 다시 탐색깊이를 +1 하여 dfs를 탐색한다.

 - visit를 설정하여 중복탐색하지 않도록 방지한다.

5. 모든 티켓을 탐색, 즉 dfs의 깊이(cnt)가 티켓의 갯수(target)와 동일할 경우, 모든 탐색이 끝난것이므로 종료한다.

 

이 경우, 알파벳 순으로 우선한 결과를 리턴하는 것이므로 첫번째로 나온 결과가 답이다. (1.과정에서 알파벳 순으로 정렬을 이미 했기 때문)

 

 

[C++ 코드]

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

using namespace std;
vector<string> answer;
vector<vector<string>> copy_tickets;
bool visit[10001];

bool dfs(string start, int cnt, int target) {
    answer.push_back(start);
    
    if(cnt == target) {
        return true;
    }
    
    for(int i=0; i<target; i++) {
        if(start == copy_tickets[i][0] && visit[i] == false) {
            visit[i] = true;
            if(dfs(copy_tickets[i][1], cnt+1, target)) {
                return true;
            }
            else {
                visit[i] = false;
            }
        } 
    }
    answer.pop_back();
    return false;   
}

vector<string> solution(vector<vector<string>> tickets) {

    copy_tickets = tickets;
    
    sort(copy_tickets.begin(), copy_tickets.end());
    
    dfs("ICN", 0, size(tickets));
    
    return answer;
}

[Python3 코드]

visit = [False]* 10001
answer = []

def dfs(start, cnt, target, tickets):
    answer.append(start)
    
    if(cnt == target):
        return True
    
    for idx, ticket in enumerate(tickets):
        if(ticket[0] == start and visit[idx] == False):
            visit[idx] = True
            if(dfs(ticket[1], cnt+1, target, tickets)):
                return True
            else:
                visit[idx] = False
    
    answer.pop()
    return False
            

def solution(tickets):
    tickets.sort()

    dfs("ICN", 0, len(tickets), tickets)
    
    return answer