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

문제

문제 링크 : 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
[[ICN, JFK], [HND, IAD], [JFK, HND]]	[ICN, JFK, HND, IAD]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

 

풀이

우선 공항에서 -> 공항으로 이동하는 경로들이 나와있기 때문에 방향성 그래프이고, 가는 경로가 다양하다.

따라서 해시맵을 사용해서 그래프를 구현하고자 했다. 각 키 공항별로 갈 수 있는 공항들을 리스트로 저장했다.

그렇다면 여기서 모든 티켓을 사용하려면 (모든 edge를 다 탐색) DFS를 사용해야겠다는 생각이 들었다.

하지만 여기서 문제점은 겹치는 경로의 티켓이 있고 (A-B, A-B), DFS의 특성상 방문한 곳을 어떻게 표시할 것이냐였다.

그래서 출발지+도착지가 키인 해시맵을 새로 만들어서 잔여 티켓의 개수를 관리했다.

재귀함수 형식으로 구성했는데, 티켓이 총 n장이면 모두 사용했을때 n+1개의 공항을 들리므로 n+1을 종료조건으로 하고,

키의 사용여부를 판단해서 그 다음 탐색을 하게 진행시켰다.

문제를 풀면서 막혔던 부분으로는 처음엔 문자열을 합쳐서 키를 만들때 StringBuilder 객체를 선언해서 여기다가 합치고, 비우고 하는 형식으로 사용했는데, 아무래도 재귀로 작동하다보니 키가 중간에 꼬여서 원하는 결과가 나오지 않았다.

따라서 매번 새 String을 선언해서 키로 사용했다.

 

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Stack;
class Solution {
	
	HashMap<String, ArrayList<String>> maps;
	HashMap<String, Integer> used;
	StringBuilder sb = new StringBuilder();	
	Stack<String> answer = new Stack<String>();
	
	int size;
	
    public String[] solution(String[][] tickets) {
    	size = tickets.length;
    	makeMap(tickets);
    	Find("ICN");
    	return answer.toArray(new String[answer.size()]);
    }
    
    public void makeMap(String[][] tickets) {
    	
    	maps = new HashMap<String, ArrayList<String>>();
    	used = new HashMap<String, Integer>();
    	
    	
    	//지도화
    	for(int i=0; i<tickets.length; i++) {
    		//공항별로 갈수 있는 공항
    		
    		if(maps.containsKey(tickets[i][0])){
    			maps.get(tickets[i][0]).add(tickets[i][1]);
    			
    		}
    		else {
    			maps.put(tickets[i][0], new ArrayList<String>());
    			maps.get(tickets[i][0]).add(tickets[i][1]);
    		}
    		
    		
    		//티켓 사용여부
    		sb.append(tickets[i][0]);
    		sb.append(tickets[i][1]);
    		
    		if(used.containsKey(sb.toString())) {
    			used.put(sb.toString(), used.get(sb.toString())+1);
    		}
    		else {
    			used.put(sb.toString(), 1);
    		}
    		
    		sb.setLength(0);
    		
    	}

    	//티켓들 정렬
    	for (ArrayList<String> dests : maps.values()) {
            Collections.sort(dests);
        }
    }
    
    public void Find(String from){
    	answer.push(from);
    	
    	if(answer.size() == size+1) return;
    	ArrayList<String> airports = maps.get(from);
    	
    	if(airports != null) {
    		
    		for(int i=0; i<airports.size(); i++) {
        		
        		String key  = from+airports.get(i);
        		
        		if(used.get(key)== 0) {
        			continue;
        		}
        		
        		used.put(key, used.get(key)-1);
        		Find(airports.get(i));
        		//return되어서 온 애들 마지막으로 return
        		if(answer.size() == size+1) return;
        		used.put(key, used.get(key)+1);
        	}
    		
    	}
    	
    	answer.pop();
    }
}

 

결과