[ 알고리즘 ] 코딩 - Programmers - 여행경로.java

---

문제 링크

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

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

---

개요

프로그래머스 - Level 3 - (자바) 여행경로 - DFS / 백트래킹 / 가지치기

---

로직 

Step 01. DFS에서 나온 결과 값이 최선인 경우를 찾기 위해 도착지를 기준으로 정렬 Step 02. 모든 "ICN" 출발지를 기준으로 탐색 시작 Step 03. StringBuilder를 이용해서 문자열을 다음 DFS로 넘겨가면 탐색 Step 03-1. DFS로 넘어가기 전에 방문 체크 로직 수행 Step 04. 다음 탐색을 진행하기 전에 사전순 가장 앞의 문자열과 비교 및 가지치기            ( Step 02에서 나온 진행물들과 최소 거리 간 비교 / String의 compareTo 이용 )  Step 05. DFS를 모두 수행했을때 미방문한 출발지가 있는지 체크. 미방문한 곳이 있다면 재탐색 Step 06. DFS를 모두 수행했을때 미방문한 출발지가 없이 문자열이 만들어졌다면, 해당 출발지에서 나올 수 있는 최소의 거리 Step 07. StringBuilder resMin의 문자열을 ","로 split하면 정답!

 

최소를 저장하는 전역 변수인 resMin을 출발지 체크 할 때마다 초기화를 해줬었다.. 찾는데 한참 걸렸다 ㅠㅠ... 조금 더 효율적이고 보기쉬운 코드를 작성하도록 노력해야겠다!

---

코드

import java.util.Arrays;
class Solution {
	        private static StringBuilder resMin;
	        public String[] solution(String[][] tickets) {
	    	int size = tickets.length;
	    	
	    	// 도착지 기준으로 정렬.
	    	Arrays.sort(tickets, (o1, o2)-> o1[1].compareTo(o2[1]));
	    	resMin = new StringBuilder("ZZZ");
	    	
	    	for(int i = 0; i < size; i++) {
	    		boolean[] selected = new boolean[size]; // 방문체크
	    		
	    		if(tickets[i][0].equals("ICN")) {
	    			// 모든 ICN 출발지 검사
	    			StringBuilder sb = new StringBuilder("ICN,");
	    			selected[i] = true;
	    			dfs(sb, tickets, tickets[i][1], 1, size, selected, i);
	    			selected[i] = false;
	    		}
	    	}
	    	
	        String[] answer = resMin.toString().split(",");
	        return answer;
	    }
	    
	    /*
	     * DFS - 깊이 우선 탐색
	     * 정렬을 한 채로 탐색을 하기 때문에 가장 먼저 만들어진 문자열이 최소.
	     * StringBuilder를 이용해서 문자열을 만들면서 진행
	     * selected를 이용해서 방문 체크
	     * */
		private boolean dfs(StringBuilder sb, String[][] tickets, String to, int idx, int size, boolean[] selected, int lock) {
			// 가지치기. 현재 사전순으로 가장 작은 문자열과 비교. 크면 진행 X
			if(sb.toString().compareTo(resMin.toString()) > 0) {
				return false;
			} 
			if(idx == size) { // 기저 조건
				for(int i = 0; i < size; i++) {
					if(!selected[i]) {
						return false;
					}
				}
				sb.append(to);
				resMin = new StringBuilder(sb);
				return true;
			}
			for(int i = 0; i < size; i++) { // 탐색 조건
				if(tickets[i][0].equals(to)) {
					StringBuilder next_sb = new StringBuilder(sb);
					next_sb.append(tickets[i][0]+",");
					boolean flag = false;
					if(selected[i]) flag = true; // 방문하기 전에 이미 방문 한 적이 있는 경우
					selected[i] = true;
					if(dfs(next_sb, tickets, tickets[i][1], idx+1, size, selected, lock)) {
						return true;
					}
					if(!flag) selected[i] = false; // 방문 해제 하면 안된다.
					selected[lock] = true;
				}
			}
			return false;
		}
	}

---