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

문제 링크

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

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

 

DFS(깊이 우선 탐색)방식에 착안하여 풀이하였다.

 

풀이 방식

 

1. boolean 배열을 선언하여 한번 산 티켓은 표시할 수 있도록 설정한다.

2. route 문자열을 선언하여 지나가는 공항 이름을 하나씩 붙여 경로를 설정할 수 있도록 한다.

3. ArrayList<String> 리스트를 선언하여 모든 공항을 들르는 루트를 다 저장할 수 있도록 한다.

   (티켓을 다 소지하여 모든 공항에 들르는 경로는 여러 개일 수가 있다.)

4. 재귀함수 dfs를 호출한다.

 4-1. 티켓을 사지 않았고(boolean 배열이 false), 내가 출발하려는 공항과 이름이 같은 경우, 티켓을 구매(boolean[i]=true)하고 해당 티켓의 도착지를 다시 출발지로 설정한다.

 4-2. 새로운 출발지를 지나갈 때마다(재귀가 호출될 때마다) route에 출발지를 append한다.

 4-3. 모든 티켓을 다 산 경우, 해당 경로를 routes에 추가한다.

 4-4. 만약 티켓을 사다 경로가 끊기게 되면 다시 이전 경로로 돌아오게 된다.(재귀 호출이 끝났으니)

5. 모든 경로를 다 구한 후, routes의 경로 중, 알파벳이 앞서는 순을 우선시하라는 문제의 조건에 따라, Sort로 오름차순 정리 후 가장 맨앞 원소를 꺼내 answer배열에 경로를 가공하여 반환한다.

 

//깊이 우선 탐색 dfs
//인접한 노드 담을때 기준은 알파벳순
//내 기준으로 인접한 노드가 있는 경우만 값에 담기
//한번 쓴 티켓은 삭제
import java.util.*;

class Solution {
    ArrayList<String> routes = new ArrayList<>();
    String route = "";
    public void dfs(String[][] tickets, String start, boolean[] soldout, int depth) {
        route += start + " ";
        if (depth == tickets.length) {
            routes.add(route);
            return;
        }
        for (int i = 0; i < tickets.length; i++) {
            if (soldout[i] == false && tickets[i][0].equals(start)) {
                soldout[i] = true;
                dfs(tickets, tickets[i][1], soldout, depth + 1);
                route = route.substring(0, route.length() - 4);
                soldout[i] = false;
            }
        }
    }
    public String[] solution(String[][] tickets) {
        boolean[] soldout = new boolean[tickets.length];
        dfs(tickets, "ICN", soldout, 0);
        Collections.sort(routes);
        route = routes.get(0);
        String[] answer = route.split(" ");
        return answer;
    }
}

 

필자의 경우, 처음엔 route 경로를 ArrayList로 해서 경로를 하나씩 원소로 담으려고 했지만, 테스트케이스에 걸렸다. 아마 여러 경로가 존재하는 경우 한번에 담을 수 없는 문제였던 것 같다.

따라서 경로를 String 으로 선언해서 AAA BBB CCC 를 지나가는 경우 각 문자열을 띄어쓰기와 함께 이어붙여준 후 split을 사용하여 다시 가공하는 방식을 택했다.