[프로그래머스] 알고리즘 고득점 kit - 여행경로 (DFS)

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164 

 

DFS(Depth First Search)를 선택한 이유

모든 항공권을 사용해야 하므로

백트래킹을 지원하고,

가능한 모든 경로를 고려하면서

끝까지 탐색하는 DFS 가 더 적합하다고 판단

 

 

트리가 아닌 그래프 구현을 선택한 이유

1.                                                                     

하나의 공항에서

여러 다른 공항으로 갈 수도,

<같은 공항을 여러 번 방문할 수도 있기에

그래프로 표현하는 것이 더 적합하다고 판단

(복잡한 구조는 그래프가 더 적합)

 

2.                                                                    

한 개의 노드가 하나의 부모 노드만

가질 수 있는 트리의 특성상

해당 문제에는 부적합하다고 판단

 

3.                                                                    

사이클을 허용하지 않는 트리의 특성상

사이클이 발생할 수도 있는

해당 문제에는부적합하다고 판단

 

 

Answer Code

public class Solution {
	public String[] solution(String[][] tickets) {
    
		boolean[] vistedFlag = new boolean[tickets.length]; // 방문 여부 체크
		ArrayList<String> possibleRoutes = new ArrayList<>(); // 가능한 모든 경로들

		Arrays.sort(tickets, (a, b) -> a[1].compareTo(b[1])); // 시작 전 정렬(알파벳 순)
		dfs("ICN", "ICN", tickets, 0, vistedFlag, possibleRoutes); // ICN에서 시작하는 DFS

		Collections.sort(possibleRoutes); // 알파벳 순 정렬
		return possibleRoutes.get(0).split(" "); // 첫번째 경로 배열로 반환
	}

	private void dfs(String currentAirport, String stackedRoute, String[][] tickets, 
		int currentLegnth, boolean[] vistedFlag, List<String> possibleRoutes) {
        
		int ticketsLength = tickets.length; // 메모리 향상

		if (currentLegnth == ticketsLength) { // 끝까지 탐색 완료 (모든 티켓 사용)
			possibleRoutes.add(stackedRoute);
			return;
		}

		for (int i = 0; i < ticketsLength; i++) {
			// 출발지가 일치하고, 아직 방문하지 않았다면
			if (currentAirport.equals(tickets[i][0]) && !vistedFlag[i]) { 
				vistedFlag[i] = true;
                
				dfs(tickets[i][1], stackedRoute + " " + tickets[i][1], tickets, 
					currentLegnth + 1, vistedFlag, possibleRoutes); // 재귀함수
                    
				vistedFlag[i] = false;
			}
		}
	}

	public static void main(String[] args) {
    
		Solution solution = new Solution();
        
		String[][] tickets1 = { { "ICN", "JFK" }, { "HND", "IAD" }, { "JFK", "HND" } };
		String[][] tickets2 = { { "ICN", "SFO" }, { "ICN", "ATL" }, { "SFO", "ATL" },
			{ "ATL", "ICN" }, { "ATL", "SFO" } };

		System.out.println(Arrays.toString(solution.solution(tickets1)));         
		System.out.println(Arrays.toString(solution.solution(tickets2))); 
	}
}

/*
 * [ICN, JFK, HND, IAD] 
 * [ICN, ATL, ICN, SFO, ATL, SFO] 
 */

 

 

가장 핵심인

dfs 메소드를 바탕으로

흐름을 살펴보자면

 

 

<첫 번째 dfs 호출>

currentAirport = "ICN"

stackedRoute = "ICN"

currentLength = 0

 

for 루프

i = 0

tickets[0] = ["ICN","JFK"]

currentAirport, tickets[0][0] = "ICN"

visitedFlag[0] = false

dfs 재귀 호출

visitedFlag[1] = true

stackedRoute = "ICN JFK"

currentLength = 1

 

 

<두 번째 dfs 호출>

currentAirport = "JFK"

stackedRoute = "ICN JFK"

currentLength = 1

 

for 루프

i = 0

visitedFlag[0] = true

i = 1

tickets[1] = ["HND","IAD"]

currentAirport = "JFK"

tickets[1][0] = "HND"

currentAirport ≠ tickets[1][0]

i = 2

tickets[2] = ["JFK","HND"]

currentAirport, tickets[2][0] = "JFK"

visitedFlag[2] = false

dfs 재귀 호출

visitedFlag[2] = true

stackedRoute = "ICN JFK HND"

currentLength = 2

 

 

<세 번째 dfs 호출>

currentAirport = "HND"

stackedRoute = "ICN JFK HND"

currentLength = 2

 

for 루프

i = 0

visitedFlag[0] = true

i = 1

tickets[1] = ["HND", "IAD"]

currentAirport,tickets[1][0] = "HND"

visitedFlag[1] = false

dfs 재귀 호출

visitedFlag[1] = true

stackedRoute = "ICN JFK HND IAD"

currentLength = 3

 

 

<네 번째 dfs 호출>

currentAirport = "IAD"

stackedRoute = "ICN JFK HND IAD"

currentLength = 3 = ticketsLength

∴  possibleRoutes = "ICN JFK HND IAD"

 

<백 트래킹>

가장 최근에 호출했던 재귀로 돌아가

visitedFlag[i] = false 로 만들고

다른 경로 탐색