프로그래머스 - 여행경로,DFS,백트래킹, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,backtracking,깊이우선탐색

 

// DFS 문제에서 backtracking인 것은 알았는데, stack으로 푸려다가 며칠간 고통받다가 그냥 재귀로 품

// Process
// 1. Input tickets, make map<공항이름, 연결된 공항이름들 리스트>
// 2. Sort adjacents (알파벳순으로 들러서 먼저 나오는 것을 찾아가도록)
// 3. DFS, backtracking. Start from ICN
// 4. Return airport names

 

포인트는.. 안쓰는 티켓이 없어야 한다는 것.

그래서, DFS로 돌면서 그냥 연결된 공항을 그냥 다 순회한다는 개념이 아니라..

 - 각 공항에서 연결된 공항을 따라가면서 방문한 공항은 제거해준다(방문 제외 개념).

 - 이 때, 더이상 공항에서 연결되어 방문할 공항이 없으면, 모든 티켓을 쓴 상황이어야 한다

 (내가 푼 방법에서는, 들른 공항이름 리스트의 길이가 티켓길이+1 이 되어야 한다는 것. 이게 그 백트래킹에서는 기저사례라고 한다.)

 

방문한 공항은 또 방문하기도 해서 visit 배열 같은 것을 따로 만들지는 않았고, 그냥 Map의 키 밸류가 있으면,

밸류의 공항이름 리스트에서 공항이름 값을 뺐다가 백트래킹 할 때 다시 넣어주는 식으로 구현했다.

 

package algorithm_sites.programmers;

import java.util.*;

class dfs_bfs_04_TravelRoute {

    public static void main(String[] args) {

        // String[][] input = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
        // String[][] input = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"},
        //                     {"ATL", "ICN"}, {"ATL", "SFO"} };

        String[][] input = {{"ICN", "COO"}, {"ICN", "BOO"}, {"COO", "ICN"}, {"BOO", "DOO"}};

        String[] answer = solution(input);

        System.out.println("");
        for (int i = 0; i < answer.length; ++i) {
            System.out.print(answer[i] + " ");
        }System.out.println("");
        
    }

    static int totalCount;
    static Map<String, List<String>> map = new HashMap<>();

    public static String[] solution(String[][] tickets) {
        String[] answer = new String[tickets.length + 1];

        totalCount = tickets.length;
        
        for (int i = 0; i < tickets.length; ++i) {
            String from = tickets[i][0];
            String to = tickets[i][1];

            if (!map.containsKey(from)) {
                map.put(from, new ArrayList<>());
            }
            if (!map.containsKey(to)) {
                map.put(to, new ArrayList<>());
            }
            map.get(from).add(to);
        }

        Iterator<List<String>> iter = map.values().iterator();
        while (iter.hasNext()) {
            Collections.sort(iter.next());
        }
        
        List<String> order = new ArrayList<>();
        dfs("ICN", order, 1);

        for (int i = 0; i < order.size(); ++i) {
            answer[i] = order.get(i);
        }
        return answer;
    }

    public static boolean dfs(String from, List<String> order, int depth) {
        order.add(from);

        if (order.size() == totalCount+1) {
            // System.out.println("=========Found");
            return true;
        }

        List<String> adjacents = map.get(from);
        for (int i = 0; i < adjacents.size(); ++i) {
            String temp = adjacents.remove(i);

            if (!dfs(temp, order, depth+1)) {
                adjacents.add(i, temp);
                order.remove(order.size()-1);
            } else {
                return true;
            }
        }
        return false;
    }

}

 

2021.05.18 - [Programming] - Git Merge vs Squash and merge(Squash) vs Rebase and merge(Fast forward) 차이점, pull request, 풀리퀘스트 병합 방법 차이점

Git Merge vs Squash and merge(Squash) vs Rebase and merge(Fast forward) 차이점, pull request, 풀리퀘스트 병합 방법

 

2021.05.12 - [Programming/Java] - Java의 equals, == 연산자와 String의 비교, JVM의 Heap 과 Constant Pool, Stack 등..

Java의 equals, == 연산자와 String의 비교, JVM의 Heap 과 Constant Pool, Stack 등..

2021.04.28 - [Algorithm/Baekjoon_acmicpc] - 백준 1700 - 멀티탭스케줄링, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy, baekjoon, bfs,dfs,acmicpc

백준 1700 - 멀티탭스케줄링, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이