[Programmers] 여행경로

[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 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 map = new HashMap<>();//(k, v) -> (도시 번호, 도시명) static Map map_reverse = new HashMap<>(); //(k, v) -> (도시명, 도시 번호) static List[] list = new ArrayList[10000]; //도시의 인접리스트 static List 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(); initList(tickets); for(int i=0; i 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

from http://dev-gorany.tistory.com/346 by ccl(A) rewrite - 2021-10-03 16:27:32