프로그래머스 (C/C++, Java) 43164 : 여행경로

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

프로그래머스

 

---

풀이

처음엔 알파벳 순으로 정렬한 후 BFS로 탐색했으나, 이렇게 탐색할 경우 답이 없는 경우를 파악하기 어려웠다.

그래서 다른 사람의 풀이를 본 후, 알파벳 순으로 정렬 후 DFS로 탐색하며 답이 아니라면 백트래킹으로 탐색하는 방법을 사용했다.

---

C/C++ 코드

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

using namespace std;

bool visited[20001];
vector<string> answer;

bool dfs(vector<vector<string>>& tickets, string now) {
    answer.push_back(now);
    for (int i = 0; i < tickets.size(); i++) {
        vector<string> t = tickets[i];
        if (t[0] == now && !visited[i]) {
            visited[i] = true;
            
            if (!dfs(tickets, t[1])) {
                visited[i] = false;
                answer.pop_back();
            }
        }
    }
    
    if (answer.size() != tickets.size() + 1)
        return false;
    return true;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    
    dfs(tickets, "ICN");
    return answer;
}

 

Java 코드

import java.util.*;

class Solution {
    
    List<String> answer = new ArrayList<>();
    boolean[] visited;

    boolean dfs(String[][] tickets, String now, int cnt) {
        answer.add(now);
        
        if (cnt == tickets.length + 1)
            return true;

        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(now) && !visited[i]) {   
                visited[i] = true;
                if (dfs(tickets, tickets[i][1], cnt + 1)) 
                    return true;
                
                answer.remove(answer.size() - 1);
                visited[i] = false;
            }
        }
        return false;
    }
    
    public String[] solution(String[][] tickets) {
        Arrays.sort(tickets, (a, b) -> {
            if (a[0].equals(b[0])) {
                return a[1].compareTo(b[1]);
            } else {
                return a[0].compareTo(b[0]); 
            }
        });
        visited = new boolean[tickets.length];
        
        dfs(tickets, "ICN", 1);
        return answer.toArray(new String[0]);
    }
}