[프로그래머스] 여행경로(43164)_DFS

문제

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

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

문제 설명

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

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

 

제한사항

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

입출력 예

	tickets	return
예제1	[[ICN, JFK], [HND, IAD], [JFK, HND]]	[ICN, JFK, HND, IAD]
예제2	[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

 

코딩풀이

import java.util.Arrays;
import java.util.PriorityQueue;

class P implements Comparable<P>{
	int index;
	String area;
	public P(int index, String area) {
		this.index=index;
		this.area=area;
	}
	@Override
	public int compareTo(P o) {
		String[] arrComparTo = new String[2];
		arrComparTo[0] = this.area;
		arrComparTo[1] = o.area;
		Arrays.sort(arrComparTo);
		if(arrComparTo[0].equals(this.area)) {
			return -1;
		}
		return 1;
	}
}

public class Solution_43164 {

	static final String StartArea = "ICN";
	
	static String[] answer;
	static boolean isEnd=false;
	
	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"}};
		String tickets[][] ={ { "ICN", "COO" }, { "ICN", "BOO" }, { "COO", "ICN" } };
		String[] answer = solution(tickets);
		print(answer);
	}
	public static String[] solution(String[][] tickets) {
        answer = new String[tickets.length+1];
        boolean[] used = new boolean[tickets.length];
        String[] tempAnswer = new String[tickets.length+1];
        dfs(tickets,StartArea,0,tempAnswer,used);
        return answer;
    }
	public static void dfs(String[][] tickets, String startArea, int cnt, String[] tempAnswer, boolean[] used) {
		if(isEnd) {
			return;
		}
		if(cnt==tickets.length) {
			if(usedAllTickets(used)) {
				tempAnswer[cnt] = startArea;
				answer = tempAnswer;
				isEnd=true;
			}
			return;
		}
		
		tempAnswer[cnt] = startArea;
		PriorityQueue<P> q = new PriorityQueue<P>();
		for(int i=0;i<tickets.length;i++) {
			if(startArea.equals(tickets[i][0]) && !used[i]) {
				q.add(new P(i, tickets[i][1]) );			
			}
		}
		while(!q.isEmpty()) {
			P p = q.poll();
			used[p.index] = true;	
			dfs(tickets,p.area,cnt+1,tempAnswer,used);
			used[p.index] = false;
		}
	}
	public static boolean usedAllTickets(boolean used[]) {
		int usedCnt = 0;
		boolean isTrue = false;
		for(int i=0;i<used.length;i++) {
			if(used[i]) {
				usedCnt++;				
			}
		}
		if(usedCnt==used.length) {
			isTrue = true;
		}
		return isTrue;
	}
	public static void print(String[] answerArr) {
		for(int i=0;i<answerArr.length;i++) {
			System.out.print(answerArr[i]+" ");
		}
		System.out.println();
	}
}

 

풀이 원리

* 최초 설정

1. 정답은 tickets 배열보다 1이 크다. 

2. 사용한 tickets은 다시 사용하지 않아야하기 때문에 boolean 1차원 배열을 생성(used)

 

* dfs 함수 내부 프로세스

3. 깊이 우선 탐색(dfs) 함수를 사용해서 cnt 를 증가시키며, tickets 배열과 동일한 크기가 되었을 때 return 한다.

4. dfs 함수 안에서는 tickets[i][0] 과 startArea(초기값 "INC") 을 탐색해서 PriorityQueue 에 넣는다.

5. PriorityQueue 에 들어가는 값은 P 이며, P 라는 class 는 index 값(used를 체크하기 위한 용도)과 area 값(다음장소)를 적재한다. 이 때,  Comparable<> 를 상속받아 정렬 처리를 해준다. compareTo(P o) 함수 참고

6. PriorityQueue 에서 하나씩 꺼내어 used 를 true로 체크하고 재귀함수를 사용해 다시 dfs 를 호출해준다.

7. 이후, used 를 false 로 변경하고 다시 PriorityQueue 를 꺼내는 작업을 반복한다.

 

* return 값

8. usedAllTickets 함수를 통해서 모든 티켓을 다 사용했는지를 체크한다.(중복 체크하는 것이라 생각됨)

9. tempAnswer[cnt] = startArea; 를 통해서 마지막 방문지를 넣는다.

10. answer 값에 넣는다.

11. isEnd=true; 를 통해서 알파벳 순서가 앞서는 경로만을 return 하도록 처리한다.