[프로그래머스] 여행경로-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을 사용하여 다시 가공하는 방식을 택했다.