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

문제내용

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

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

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

---

문제 접근 방법

결론부터 말하자면 이문제는 백트래킹을 활용해야 풀 수 있는 문제이다.

처음엔 백트래킹을 고려하지 않고 단순히 DFS 방식으로 풀려고 했고 백트래킹 방식을 고려하지 않고 풀었을때 테스트케이스 1번에서 실패가 나왔다. 이유는 내가푼 풀이를 생각해보면 답이 나온다.

 

내가 풀었던 풀이는 무조건 "ICN"에서 출발하기 때문에 "ICN"이 출발지로 돼있는 티켓중 도착지의 알파벳 순서가 가장 빠른 티켓을골라 dfs를 시작했고, dfs안에서도 compareTo를 이용해 도착지를 알파벳순서로 나올수 있게끔하는 방식을 택하고, 모든 티켓을 사용한 경우라면 끝내는 dfs를 끝내는 방식으로 코드를 작성했다.

 

이렇게 풀면 문제가 발생하는데 예를들어 "{{"ICN", "B"}, {"B", "ICN"}, {"ICN", "A"}, {"A", "D"}, {"D", "A"}}" 의 경우

"ICN B ICN A D A" 라는 여행경로가 나와야한다. 하지만 내가짠 코드에서는

"ICN A D null null null" 이라는 결과가 나온다. 이유는 출발지 "ICN"의 티켓중 도착지가 가장 빠른게 "A" 이기 때문에 첫 티켓으로 {"ICN", "A"} 를 사용하고 {"A", "D"}, {"D", "A"} 순서로 티켓을 사용하게 된다. 그리고 나선 이제 출발지가 "A"로 돼있는 티켓을 전부 사용했기때문에 뒤에는 null로 결과가 나오게 된다.

 

따라서 이문제는 첫 출발지가 "ICN"인 티켓을 시작으로하는 모든 경로의 경우의수를 조합해보고 조합해서 나온 경로중 알파벳 순으로 가장 빠른 경로를 택해야하는 방법이 필요하다. 그래서 백트래킹인 것이다.

 

자세한 설명은 주석을 달아놨고

풀이를 보고 생각해보자.

 

---

풀이

백트래킹 풀이

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	static boolean[] check;//방문 배열
	static ArrayList<String> answer;//여행 경로를 저장해놓을 리스트
	public static String[] solution(String[][] tickets) {
		check = new boolean[tickets.length];
		answer = new ArrayList<String>();
		int cnt = 0;//티켓 몇개를 사용했는지 알려줄 변수
		
		//tripDFS(cnt변수, 출발지(start), 여행경로(seq), 티켓);
		tripDFS(cnt, "ICN", "ICN", tickets);
		Collections.sort(answer);//알파벳 순으로 여행 경로를 오름차순 정렬
		
		/* 정렬 후 가장 앞에 있는 여행경로가 알파벳순서가 빠른걸로 분류된 여행경로가됨.
		 * 정답은 반환값이 String배열이라 String배열에 넣어줌.
		 */
		String[] result = answer.get(0).split(" ");
		
		return result;
	}
	
	public static void tripDFS(int cnt, String start, String seq, String[][] tickets) {
		if(cnt == tickets.length) {//티켓을 다 사용했다면
			answer.add(seq);//여행경로 리스트에 하나 완성된 seq 추가.(경우의수 하나 추가)
			return;
		}
		
		for(int i=0; i<tickets.length; i++) {
			//i번째 티켓 사용안했고, start와 i번재 티켓의 출발지가 같으면
			if(!check[i] && start.equals(tickets[i][0])) {
				check[i] = true;//사용처리
				/*
				 * 1.티켓 하나 사용했기 때문에 cnt+1.
				 * 2.start는 지금 사용한 티켓의 도착지로 변경돼야 지금 도착지가 출발지로 적힌 티켓 활용가능함
				 * 따라서 start는 tickets[i][1]으로 갱신.
				 * 3.여행경로는 지금까지 추가된 경로 seq에 지금 사용한 티켓의 도착지를 추가.
				 * 4.tickets 배열은 그대로 넣줌. 그냥 티켓 뭐있는지 확인용도.
				 */
				tripDFS(cnt+1, tickets[i][1], seq+" "+tickets[i][1], tickets);
				
				check[i] = false;//모든 경우의 경로를 알아봐야하기 때문에 dfs 끝나면 false처리.
			}
		}
		
		return;//for문 끝나면 종료.
	}
}

 

내가했던 풀이(틀림)

참고로 내가한 풀이는 주석안달았음.

public class Solution {
	static boolean[] check;
	static String[] answer;
	public static String[] solution(String[][] tickets) {
		answer = new String[tickets.length+1];
		check = new boolean[tickets.length];
		String end = "";
		int idx = 0;
		for(int i=0; i<tickets.length; i++) {
			if(!tickets[i][0].equals("ICN")) {continue;}
			else {
				end = tickets[i][1];
				idx = i;
			}
			
			for(int j=0; j<tickets.length; j++) {
				if(i==j) {continue;}
				if(tickets[j][0].equals("ICN")) {
					if(end.compareTo(tickets[j][1]) > 0) {
						end = tickets[j][1];
						idx = j;
					}
				}
			}
		}

		answer[0] = tickets[idx][0];
		tripDFS(idx, tickets, 1);

		for(String a:answer) {
			System.out.print(a+" ");
		}
		return answer;
	}
	
	public static void tripDFS(int v, String[][] tickets, int depth) {
		check[v] = true;
		String start = "";
		String end = "";
		int idx = 0;
		
		if(depth==answer.length-1) {
			answer[depth]=tickets[v][1];
		}
		for(int i=0; i<tickets.length; i++) {
			if(check[i]) {continue;}
			if(tickets[v][1].equals(tickets[i][0])) {
				start = tickets[i][0];
				end = tickets[i][1];
				idx = i;
			}else {
				continue;
			}
			for(int j=0; j<tickets.length; j++) {
				if(check[j] || i==j) {continue;}
				
				if(start.equals(tickets[j][0])) {
					if(end.compareTo(tickets[j][1])>0) {
						end = tickets[j][1];
						idx = j;
					}
				}
			}
			answer[depth]=tickets[idx][0];
			
			tripDFS(idx, tickets, depth+1);
		}
	}
}

 

---

마치며

나는 여태까지 DFS랑 백트래킹을 분리시켜 생각하고 있어서 DFS로 풀어라! 라고 말하면 그냥 단순 DFS로만 풀려고 했는데 그게 아니라는걸 알게됐다. 사실 생각해보면 백트래킹도 DFS의 한종류라는것.. ㅎㅎ

여튼 덕분에 삽질도 좀 했지만 백트래킹을 다시 공부해볼수 있어서 좋았다.