[Java] 깊이/너비 우선 탐색(DFS/BFS) - 여행경로 (Lv3)

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

프로그래머스

 

 

✔ 입출력 예시

여행경로 입출력 예시

 

💡 포인트

     1️⃣ 항상 "ICN" 공항에서 출발

     2️⃣ tickets 배열의 원소는 [출발지, 도착지] 형태로 이루어짐

     3️⃣ 주어진 항공권을 모두 사용해야 함

     4️⃣ 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return

 

 

❓ 풀이방법

     처음에는 BFS 알고리즘을 이용해볼까 생각했지만 알파벳 순서가 앞서는 경로를 답으로 구해야했기 때문에

     DFS 알고리즘을 이용하기로 결정

     1️⃣ tickets와 동일한 길이의 방문배열(v) 생성 👉 주어진 tickets를 모두 사용하기 위해

     2️⃣ 경로 탐색 👉 dfs()

     3️⃣ 기저조건은 주어진 항공권을 모두 사용하였을 때 return

           👉 answer가 비어있다면 지금까지 온 경로(path)를 answer에 할당

           👉 answer가 비어있지 않다면 지금까지 온 경로(path)와 answer를 비교하여 사전순으로 더 앞선 문자열을

                 answer에 할당

     4️⃣ tickets 배열을 순회하며, 출발지가 일치하고 사용하지 않은 항공권이라면 방문배열에 체크하고 다음 항공권으로

          넘어가기 👉 ❗ dfs() 함수에서 빠져나왔을 때를 주의하여 방문했던 항공권을 false로 반드시 다시 할당해주기

 

 

✔ 소스코드

import java.util.Arrays;

public class Solution { // 여행 경로

	public static void main(String[] args) {
		String[][] tickets = { { "ICN", "JFK" }, { "HND", "IAD" }, { "JFK", "HND" } };
//		String[][] tickets = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}};

		System.out.println(solution(tickets));
	}

	static String answer = "";
	private static String[] solution(String[][] tickets) {
		
		// 1. 항공권 체크 배열
		boolean [] v= new boolean[tickets.length];
		
		// 2. 경로 탐색
		dfs(tickets, v, "ICN", "ICN", 0);
		
		return answer.split(",");
	}

	private static void dfs(String[][] tickets, boolean[] v, String path, String dep, int cnt) {
		if(cnt == v.length) { 
			if (answer.length() == 0) {
				answer = path;			
			}else if(answer.compareTo(path) > 0) {
				answer = path;
			}
			return;
		}
		
		// 4. 배열을 순회
		for (int i = 0; i < v.length; i++) {
			if(tickets[i][0].equals(dep) && !v[i]) {
				v[i] = true;
				dfs(tickets, v, path + "," + tickets[i][1], tickets[i][1], cnt+1);
				v[i] = false;
			}
		}
	}
}

 

 

❗ 결과

     👉 테스트 통과

여행경로 실행 결과

 

⏰ 문제 풀이 시간

     👉 49분 11초

 

오늘부터 알고리즘 문제를 풀 때 시간을 재기로 했다. 이전에는 그저 혼자만의 방법을 생각하는데에 그쳤다면 이제는 코딩테스트에 대비하여 시간을 재고 푸는 습관을 들이기로 했다.

 

오늘 푼 여행경로 문제는 출발지와 도착지 그리고 티켓 사용 유무 모두를 생각해야했던 문제라 조금 헷갈렸지만 생각보다 금방 풀었던 것 같다😊