[프로그래머스] 여행경로(JAVA)

코딩테스트연습(DFS,BFS) - 여행경로

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

프로그래머스

문제 설명

티켓들이 담겨있는 tickets가 주어진다. tickets에는 출발지와 도착지 정보가 들어있다.

모든 티켓을 사용하여 여행경로를 짜는 경우를 배열로 반환하는 문제이다.

티켓은 항상 모든 티켓을 사용할 수 있도록 주어진다.

출발은 항상 ICN에서 한다.

모든 티켓을 사용하는 경로가 여러개일 경우 알파벳순으로 정렬한다.

ex)

ICN->JFK

HND->IAD

JFK->HND 가 주어질 때 

경로는 ICN->JFK->HND->IAD 이다.

 

---

문제 풀이

생각 과정

우선 dfs, 재귀함수로 구현하기로 생각했다.

ICN부터 시작하는 route를 리스트로 생성하여 재귀함수에 넣어준다.

재귀함수의 종료조건은 모든 티켓을 사용한 것이므로

route의 길이가 티켓수+1이 될 때를 종료조건으로 설정했다.

 

그 다음 모든 티켓을 순환하면서 마지막으로 방문한 도시를 출발로 하는 티켓이 나오면 route에 넣어주고

route를 재귀함수에 다시 넣는다. 티켓은 사용했으므로 boolean 배열을 하나 만들어서 중복체크를 해줘야한다.

재귀 종료조건에 도달하면 route를 정답으로 설정하고 마무리한다.

 

그러나 여기까지 진행한다면 알파벳 순서가 앞서는 경로를 출력한다는 조건을 만족시키지 못한다.

따라서 나는 티켓들을 알파벳순서로 미리 정렬해두는 작업을 했다.

방법은 아래 코드에서 보자.

---

구현

import java.util.*;
class Solution {
    static String[] answer;
    static boolean[] visit;
    public String[] solution(String[][] tickets) {
        visit = new boolean[tickets.length];	// 중복 체크 배열
        answer = new String[tickets.length + 1];	// 정답 배열
        Arrays.sort(tickets, new Comparator<String[]>() {	// 티켓을 도착지기준으로 정렬
            @Override
            public int compare(String[] o1, String[] o2) {
                return o1[1].compareTo(o2[1]);
            }
        });
        List<String> route = new ArrayList<>();	// 경로를 저장할 리스트
        route.add("ICN");	// 경로는 항상 ICN부터 시작
        dfs(route, tickets.length,tickets);
        return answer;
    }

    public void dfs(List<String> route, int ticketSize, String[][] tickets){
        if (route.size()==ticketSize+1) {	// 모든 티켓 사용
            answer = route.toArray(new String[route.size()]);
            return;
        }

        String last = route.get(route.size() - 1);	// 마지막 여행지
        for (int i = 0; i < tickets.length; i++) {
            String ticketFrom = tickets[i][0];
            if (last.equals(ticketFrom) && !visit[i]) {	// 마지막 여행지가 티켓의 출발지와 같다면
                visit[i] = true;
                String to = tickets[i][1];
                route.add(to);	// 도착지를 경로에 넣고 재귀반복
                dfs(route,ticketSize,tickets);
                if(answer[0]!=null) return;	// 정답을 이미 구한 경우 종료
                visit[i] = false;
                route.remove(route.size() - 1);
            }
        }
    }
}

회고

1. 출발지는 정렬하지 않아도 된다.

2. 리스트를 정렬해놨기 때문에 모든 루트를 구하지 않아도 된다. 
    처음 종료조건에 도달한 루트가 바로 정답이 된다.

    따라서 if(answer[0]!=null) return; 라는 종료조건을 추가했다.