[프로그래머스 : 레벨3] 여행경로 : DFS(Java)

이번문제는 여러 테스트케이스에서 생각을 하지 못해서 문제를 풀지 못했다.

그래서 결국 답지를 봤다.

 

일단 문제부터 살펴보자.

 

문제 설명

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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"]

 

입출력 예 설명

 

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

문제 풀이

나는 이번 문제의 풀이방식을 일단 출발점으로 시작하는 부분을 방문하고 그중 알파벳이 적은걸 방문해서 

결과를 모든 경로를 방문하는 방식으로 생각했다.

 

하지만 이 풀이방식은 아래와 같은 테스트케이스를 만족하지 못한다.

 

{{"ICN", "BOO"}, {"ICN", "COO"}, {"COO", "ICN"}, {"BOO", "DOO"}}

ICN -> BOO -> DOO 이렇게 되서 모든 경로를 방문하지 못하는 결과가 생긴다.

 

이부분을 혼자 해결하려고 애썼지만 결국 답지를 봤다.

 

내가 본 답지의 풀이과정은 아래와 같았다.

 

모든 노드의 방문 결과를 확인하고 그중 모든 node를 방문한것들만 list에 추가하는 방식이다.

그 다음엔 list를 알파벳순으로 정렬하여서 가장 첫번째 결과를 return 하는것이다.

 

전체 소스는 아래와 같다.

 

    public String[] solution(String[][] tickets) {
        List<String> list = new ArrayList<>(); 
        int[] visit = new int[tickets.length]; //티켓의 경로 방문 처리를 위해서
        
        dfs("ICN",0,"ICN",tickets,visit,list);
        Collections.sort(list);
        String[] result = list.get(0).split(" ");
        return result;
    }



	private void dfs(String start, int index, String result, String[][] tickets, int[] visit, List<String> list) {
		// TODO Auto-generated method stub
		if(index == tickets.length) { //모든 노드를 방문했을때 진입
			list.add(result); //list에 추가
			return;
		}
		for(int i = 0; i<tickets.length;i++) {
			if(visit[i]!= 1 && start.equals(tickets[i][0])) {
				visit[i] = 1; //방문처리했다가
				dfs(tickets[i][1],index+1,result+" "+tickets[i][1],tickets,visit,list);
				visit[i] = 0; //다시 방문안하게 해서 다른 노드에서도 사용가능하게 함
			}
		}
	}

 

 

느낀점

1. stackOverFlow 에러는 재귀호출에서 끊어지는 지점이 없을때 생기는 오류이다.

2. 많은 테스트케이스를 생각해보자.

3. 특정경우에서 모든 노드를 방문한것만 추가하고 싶을땐 index를 활용하여서

index == arr.length 해서 해당 경우에만 값을 집어 넣는걸로 해라.

4. 모든 조합을 확인하고 싶을땐 방문 처리후 dfs 재귀호출한다음에 방문 처리 한것을 방문 안함으로 바꿔라