프로그래머스 (Level 3) - 여행경로

문제 설명

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

 

풀이

주어진 항공권 정보를 이용해 방문하는 공항 경로를 찾아내는 문제이다.

 

방문 가능한 경로가 2개 이상일 경우 알파벳 순서로 방문을 해야 하는 조건 때문에 까다로웠던 문제이다. 해당 조건을 고려해서 방문할 수 있는 모든 여행경로를 DFS 알고리즘을 이용해서 탐색한 후 List 자료구조에 저장을 하였다.

 

모든 여행경로의 탐색이 끝났으면, List 자료구조 내의 데이터를 알파벳 순으로 오름차순을 한다. 오름차순으로 정렬된 List의 첫 번째 원소를 반환해주는 방식으로 문제를 해결하였다.

 

전체 소스코드

import java.io.*;
import java.util.*;

public class Solution03 {
	static boolean[] visited; // 각 경로의 방문 여부를 저장하기 위한 배열

	static List<String> result = new ArrayList<>();

	public String[] solution(String[][] tickets) {

		visited = new boolean[tickets.length];

		dfs("ICN", "ICN", 0, tickets);

		Collections.sort(result);

		String[] answer = result.get(0).split(" ");

		return answer;
	}

	/** dfs 알고리즘을 이용해서 모든 여행경로들을 탐색 */
	static void dfs(String start, String route, int count, String[][] tickets) {

		if (count == tickets.length) {
			result.add(route);

			return;
		}

		for (int i = 0; i < tickets.length; i++) {

			/* 아직 방문하지 않은 여행경로인 경우 */
			if (visited[i] == false && tickets[i][0].equals(start)) {
				visited[i] = true;

				dfs(tickets[i][1], route + " " + tickets[i][1], count + 1, tickets);

				visited[i] = false;
			}
		}
	}
}