[Programmers] 여행경로

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

[DFS + 백트래킹]

1) 도시에 각각 고유 번호를 부여해서 <도시명, 도시번호>, <도시번호, 도시명> 맵을 각각 만든다.

2) 도시 번호와 도시명이 있으니 티켓을 반복해 돌며 인접리스트를 만든다.

3) 탐색을 한다.

    /*
    * ticketSize = 주어진 티켓이 총 몇장인지?
    * size = 현재 티켓을 몇 장째 처리하고 있는지
    * cur = 현재 방문하고 있는 도시의 번호
    * */
    static boolean DFS(int ticketSize, int size, int cur){

        if(size > ticketSize) return true; //end point

        for(int i=0; i<list[cur].size(); i++){
            Point p = list[cur].get(i);

            if(p.check) continue; //이미 사용한 티켓이면 skip

            p.check = true;
            result.add(map.get(p.city));

            if(DFS(ticketSize, size + 1, p.city)) return true; //결과값 찾으면 end

            p.check = false;
            result.remove(size);
        }

        return false;
    }

 

List<String> result = new ArrayList<>(); //결과를 저장할 리스트

result에다가 방문한 도시를 적어줄 것이다. 그 값이 티켓 사이즈보다 크면 모든 티켓을 사용한 것이므로 종료 조건을 충족한다.

 

조금더 상세한 설명은 주석과 함께보면 좋다.

Code </>

import java.util.*;

/*
* 주어진 항공권을 모두 사용하여 여행 경로, 항상 ICN에서 출발
* 방문하는 공항 경로를 배열에 담아 반환
*
* 1. 모든 공항은 3글자
* 2. 3 ~ 10000개
* 3. [a, b]는 a -> b
* 4. 항공권 모두 사용
* 5. 경로가 2개 이상일 경우 알파벳 순
* 6. 모든 도시를 방문할 수 없는 경우는 X
* */
class Solution {

    static class Point{
        Integer city;
        boolean check;

        public Point(Integer city) {
            this.city = city;
            this.check = false;
        }
    }

    static Map<Integer, String> map = new HashMap<>();//(k, v) -> (도시 번호, 도시명)
    static Map<String, Integer> map_reverse = new HashMap<>(); //(k, v) -> (도시명, 도시 번호)
    static List<Point>[] list = new ArrayList[10000]; //도시의 인접리스트
    static List<String> result = new ArrayList<>(); //결과를 저장할 리스트

    /*
    * Map을 초기화시키는 메서드
    * */
    static int initMap(String[][] t){

        int idx = 0;
        for(String[] arr : t){
            String c1 = arr[0];
            String c2 = arr[1];

            if(!map_reverse.containsKey(c1)) {
                map.put(idx, c1);
                map_reverse.put(c1, idx++);
            }
            if(!map_reverse.containsKey(c2)) {
                map.put(idx, c2);
                map_reverse.put(c2, idx++);
            }
        }

        return idx;
    }
    /*
    * 인접리스트 초기화 메서드
    * */
    static void initList(String[][] t){

        for(String[] arr : t){
            int start = map_reverse.get(arr[0]);
            int end = map_reverse.get(arr[1]);

            list[start].add(new Point(end));
        }
    }
    /*
    * ticketSize = 주어진 티켓이 총 몇장인지?
    * size = 현재 티켓을 몇 장째 처리하고 있는지
    * cur = 현재 방문하고 있는 도시의 번호
    * */
    static boolean DFS(int ticketSize, int size, int cur){

        if(size > ticketSize) return true; //end point

        for(int i=0; i<list[cur].size(); i++){
            Point p = list[cur].get(i);

            if(p.check) continue; //이미 사용한 티켓이면 skip

            p.check = true;
            result.add(map.get(p.city));

            if(DFS(ticketSize, size + 1, p.city)) return true; //결과값 찾으면 end

            p.check = false;
            result.remove(size);
        }

        return false;
    }

    public String[] solution(String[][] tickets) {

        int ticketSize = tickets.length;
        //init map
        int count = initMap(tickets);
        //init list
        for(int i=0; i<count; i++)
            list[i] = new ArrayList<>();

        initList(tickets);

        for(int i=0; i<count; i++) //알파벳 순으로 정렬해두면 가장 먼저 탐색하는 값이 최적해 이다.
            list[i].sort((a, b) -> map.get(a.city).compareTo(map.get(b.city)));
        //search
        result.add("ICN");
        Integer icn = map_reverse.get("ICN"); //인천에서 시작

        DFS(ticketSize, 1, icn);

        //get answer
        int resultSize = result.size();
        String[] answer = new String[resultSize];

        for(int i=0; i<resultSize; i++)
            answer[i] = result.get(i);

        return answer;
    }
}

class Main{
    public static void main(String[] args) {
        String[][] t = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}};

        Solution sol = new Solution();

        String[] s = sol.solution(t);

        System.out.println("=====================");
        for(String str:s)
            System.out.println(str);
    }
}