출처: https://school.programmers.co.kr/learn/courses/30/lessons/43164
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 문제

2. 풀이
⚠ 이 문제는 주의해야 할 조건들이 몇 개 있다.
- 항상 "ICN" 공항에서 출발한다.
- 주어진 항공권을 모두 사용해야 한다.
- 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 해야 한다.
3개의 조건을 잘 염두에 두고 문제를 풀어보자.
우선, 주어진 항공권을 모두 사용해서 모든 공항을 방문할 수 있는 경로를 찾아야 하기 때문에 DFS를 떠올려 볼 수 있다.
먼저, 항공권 사용 여부를 확인할 visited 배열과, 모든 방문 경로를 담아둘 list가 필요하다.
DFS 함수의 매개변수에는 다음과 같은 값을 포함한다.
- depth : 주어진 항공권을 모두 사용했는지를 확인하기 위해서 현재까지 사용한 항공권의 개수를 카운트 해줄 변수
- now : 현재 도착한 공항이 어디인지를 나타내는 변수
- path : 방문하는 공항 경로를 담을 변수
- tickets : 항공권 정보가 담긴 배열
DFS 함수는 다음과 같이 동작한다.
tickets 배열을 돌면서 now와 출발지가 같은 항공권을 찾고, 해당 항공권이 사용되지 않았다면 사용, dfs를 다시 ㄷ돈다.
그 때 항공권을 하나 사용했기 때문에 depth는 +1 해주고, now는 현재 항공권의 도착지, path는 지금까지의 경로에 현재 항공권의 도착지를 붙인 값이 된다.
항공권을 전부 탐색해서 더이상 탐색할 항공권이 없다면, 현재까지의 path를 list에 추가하고 return 한다. 다른 경로도 탐색해야하기 때문에 항공권의 사용 여부를 false로 바꿔준다.
DFS 함수는 다음과 같이 작성할 수 있다.
public void dfs(int depth, String now, String path, String[][] tickets){
if(depth == tickets.length){
list.add(path);
return;
}
for(int i=0; i<visited.length; i++){
if(!visited[i] && now.equals(tickets[i][0])){
visited[i] = true;
dfs(depth + 1, tickets[i][1], path + " " + tickets[i][1], tickets);
visited[i] = false;
}
}
}
그렇다면 dfs 함수를 호출할 때 인자는 다음과 같이 넣어줘야 한다.
아직 항공권을 사용하지 않았기 때문에 depth는 0이 되고, 반드시 ICN에서 출발해야 하기 때문에 now는 "ICN"이 된다.
현재 위치한 ICN만 방문했기 때문에 경로도 "ICN"이 된다.
dfs(0, "ICN", "ICN", tickets);
조건 중에 "가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 해야 한다" 라는 조건이 있기 때문에 tickets 배열을 도착지를 기준으로 오름차순 정렬해준다.
Arrays.sort(tickets, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
return o1[1].toString().compareTo(o2[1].toString());
}
});
dfs를 다 돌고 나면 list에는 항공권을 모두 사용했을 때 구할 수있는 경로들이 들어가 있다.
tickets을 오름차순으로 정렬해줬기 때문에 list의 첫번째 값에는 알파벳 순서가 앞서는 경우의 경로가 들어있다.
따라서 list의 첫 번째 문자열을 공백을 기준으로 나눠 문자열 배열에 넣어 return 하면 정답이다.
3. 소스코드
위 과정을 소스코드로 전체 작성하면 다음과 같다,
import java.util.*;
class Solution {
boolean[] visited; // i번째 항공권 사용 여부
ArrayList<String> list = new ArrayList<>(); // 경로 모든 경우를 담음
public String[] solution(String[][] tickets) {
Arrays.sort(tickets, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
return o1[1].toString().compareTo(o2[1].toString());
}
});
visited = new boolean[tickets.length];
dfs(0, "ICN", "ICN", tickets);
String[] answer = list.get(0).split(" ");
return answer;
}
// depth: 탐색한 항공권의 개수
// now: 현재 위치한 공항
// path: 현재까지의 경로
public void dfs(int depth, String now, String path, String[][] tickets){
if(depth == tickets.length){
list.add(path);
return;
}
for(int i=0; i<visited.length; i++){
if(!visited[i] && now.equals(tickets[i][0])){
visited[i] = true;
dfs(depth + 1, tickets[i][1], path + " " + tickets[i][1], tickets);
visited[i] = false;
}
}
}
}

마치며 ...
처음에 dfs로 접근해서 풀었는데, 모든 항공권을 탐색해야 한다는 조건을 고려하지 못해서 2개만 맞고 2개는 틀렸었다.
문제를 풀 때 꼭 지문에 나와있는 주의사항을 잘 체크해서 조건 처리를 잘 해줘야겠다!
피드백은 언제든 환영입니다! 🙌
'Programming > Programmers' 카테고리의 다른 글
[프로그래머스] 12953번 - N개의 최소공배수 (Java) (0) | 2023.06.14 |
---|---|
[프로그래머스] 12980번 - 점프와 순간 이동 (Java) (0) | 2023.06.13 |
[프로그래머스] 12985번 - 예상 대진표 (Java) (0) | 2023.06.12 |
[프로그래머스] 43162번 - 네트워크 (JAVA) (0) | 2023.06.11 |
[프로그래머스] 12973번 - 짝지어 제거하기 (JAVA) (0) | 2023.06.08 |