프로그래머스 - 여행경로

여행경로 : https://school.programmers.co.kr/learn/courses/30/lessons/43164#

---

Problem

---

Solve

연결된 공항을 한 줄로 줄세워 경로를 만들어야 하는 걸 보고 위상정렬을 먼저 떠올렸습니다.
위상정렬을 DFS를 이용해서 중복 경로를 제외하고 구현했더니 반례로 동일한 경로의 ticket이 있었고 어떤식으로 해결할 수 있을지 고민하다가 인접리스트와 유사하게 인접 큐?로 구현해서 동일한 경로 ticket도 접근가능하도록 구현했습니다.
(사실 위상정렬이라고도 하기엔 그냥 dfs죠.. 정렬한다는 접근법만 참고해서 풀은것 같습니다ㅎ..)

풀이

먼저 연결된 공항을 정의할 PriorityQueue<String>[] linked 배열 String타입의 공항을 index로 변경해줄 Map<String,Integer> airPortNum을 정의해줍니다.

• PriorityQueue로 구현한 이유
  • 2개 이상의 경로가 있을때 알파벳 우선순위로 선정해줘야하기 때문에 연결된 공항을 정렬해주기 위함
  • 똑같은 출발 공항과 도착 공항인 티켓을 구분해서 연결하기 위함

tickets을 순환하면서 linked에 출발 공항과 연결된 공항을 linked에 저장해줍니다.

그리고 dfs로 인접한 공항을 접근하면서 더 이상 접근할 수 있는 공항이 없는 경우 stack에 차례대로 해당 공항을 저장해줍니다.

• DFS로 어떻게 경로가 되는지 이해가 안된다면 https://yoongrammer.tistory.com/86 에서 DFS구현 예시가 참고가 될것같습니다.

모든 공항을 돌아서 stack에 경로가 저장이 되었다면 마지막에 INC 공항을 저장하고 answer의 첫번째 인덱스부터 stack.pop()의 값을 저장하여 반환해줍니다.

---

Code

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Collections;
import java.util.PriorityQueue;
class Solution {
    public String[] solution(String[][] tickets) {
        Map<String, Integer> airPortNum = new HashMap<>();
		PriorityQueue<String>[] linked = new PriorityQueue[10000];
		for(int i=0;i<linked.length;i++){
			linked[i] = new PriorityQueue<>();
		}
        //공항 index
		int num = 0;
		for(String[] ticket : tickets){
			String departure = ticket[0];
			String arrival = ticket[1];
			if(!airPortNum.containsKey(departure)){
				airPortNum.put(departure, num++);
			}
			linked[airPortNum.get(departure)].add(arrival);

			if(!airPortNum.containsKey(arrival)){
				airPortNum.put(arrival, num++);
			}
		}
		
        //공항 경로 저장
		Stack<String> stack = new Stack<>();
		int start = airPortNum.get("ICN");
		dfs(linked, stack,airPortNum, start);

		String[] answer = new String[stack.size()+1];
		int index = 0;
        //출발지 INC저장
		stack.push("ICN");
		while(!stack.isEmpty()){
			answer[index++] = stack.pop();
		}

		return answer;
    }
    
    void dfs(PriorityQueue<String>[] linked, Stack<String> stack, Map<String,Integer> airPortNum, int currentAirPort){
    	//해당 공항과 연결된 공항 찾기
		while(!linked[currentAirPort].isEmpty()){
        	//알파벳이 사전순으로 가장 빠른 공항
			String linkAirPort = linked[currentAirPort].poll();
			int linkAirPortNum = airPortNum.get(linkAirPort);
            
			dfs(linked, stack, airPortNum, airPortNum.get(linkAirPort));
            
            //해당 공항을 경로로 지정한다.
			stack.push(linkAirPort);
		}
	}
}

---

Result

---

Reference

https://yoongrammer.tistory.com/86