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

코딩테스트 연습 - 여행경로 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

모든 도시를 방문할 수 있는 여행경로를 구하는 과정에 있어 출발지가 같은 티켓이 존재할 수 있다는 점을 고려하여 그래프 탐색을 진행하고 조건에 맞지 않을 경우 되돌아오는 DFS를 적용하고자 하였습니다.

ICN에서부터 시작하여 출발지 문자열이 일치하는 인덱스를 찾고, 해당 티켓을 사용하였을 경우 모든 경로를 탐색할 수 없다면 다른 티켓을 탐색하는 방식으로 진행한다면 올바른 경로를 찾을 수 있을 것이라고 생각하였습니다.

코드

import java.util.*;

class Solution {
    private static final String START = "ICN";
    private static LinkedList<String> waypoints = new LinkedList<>();
    private boolean[] used;
    private String[][] tickets;
        
    public String[] solution(String[][] tickets) {
        setTickets(tickets);
        used = new boolean[tickets.length];
        Arrays.sort(tickets, (x,y) -> x[1].compareTo(y[1]));
        waypoints.add(START);
        searchPath(START,0);
        
        return waypoints.toArray(new String[0]);
    }
    
    private boolean searchPath(String start, int count){
        if(count == tickets.length) return true;
        
        for(int i=0; i<tickets.length; i++){
            if(!used[i] && start.equals(tickets[i][0])){
                used[i] = true;
                waypoints.add(tickets[i][1]);
                boolean isCorrect = searchPath(tickets[i][1], count+1);
                if(isCorrect) return true;
                used[i] = false;
                waypoints.removeLast();
            }
        }
        return false;
    }
    
    private void setTickets(String[][] tickets){
        this.tickets = tickets;
    }
}

LinkedList를 사용하여 DFS를 구현하였습니다.

String 배열 tickets의 첫번째 원소와 출발지 문자열이 일치할 경우 LinkedList에 추가한 후 그래프 탐색을 계속 진행하고, 모든 도시를 방문할 수 없는 경우 이전 상태로 복구하여 다음 출발지를 모색합니다.

LinkedList로 DFS를 구현함에 있어 주의해야 할 점은 LinkedList의 pop, remove, poll함수는 첫번째 원소를 제거한다는 점입니다.

이전 상태로 복구하기 위해서는 remove, poll이 아닌 removeLast, pollLast 함수를 사용하여야 합니다.