알고리즘/프로그래머스
[프로그래머스] 여행경로 Java 풀이 및 해설
승민아
2024. 5. 16. 13:13
https://school.programmers.co.kr/learn/courses/30/lessons/43164#qna
풀이 방법
- DFS를 사용한다.
- dfs(남은 티켓, 현재 공항, 현재까지의 누적 경로, 정답 후보(미정렬상태), 티켓 사용 여부, 티켓)
- 모든 티켓을 사용했다면 정답 후보에 넣는다.
- 티켓 반복문을 돌며 현재 공항과 티켓에 명시된 출발지가 동일하다면 depth + 1을 한다.
- 단, 미사용 티켓이여야한다.
모든 티켓을 사용했을때 정답 후보에 경로를 ","를 구분자로 넣는다.
DFS 탐색을 종료하고 오름차순으로 정렬하고 "," 구분자가 있으므로 첫번째 스트링을 split(",")로 분리한것이 답이다.
전체 코드
import java.util.*;
class Solution {
public String[] solution(String[][] tickets) {
String[] answer;
List<String> pathList = new ArrayList<>();
boolean[] visit = new boolean[tickets.length];
dfs(tickets.length, "ICN", "ICN", pathList, visit, tickets);
pathList.sort((o1, o2) -> {
return o1.compareTo(o2);
});
answer = pathList.get(0).split(",");
return answer;
}
void dfs(int leaveTicket, String cur, String path, List<String>pathList, boolean[] visit, String[][] tickets) {
if(leaveTicket == 0) {
pathList.add(path);
return;
}
for(int i=0; i<tickets.length; i++) {
String ticketStart = tickets[i][0]; // 티켓의 출발지
String ticketGoal = tickets[i][1]; // 티켓의 목적지
if(ticketStart.equals(cur) && visit[i] == false) {
visit[i] = true;
dfs(leaveTicket-1, ticketGoal, path+","+ticketGoal, pathList, visit, tickets);
visit[i] = false;
}
}
}
}