10. DFS & BFS - 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164
DFS & BFS 여행경로

DFS, 백트래킹 재귀로 해결

재귀함수

선언부

void recursive(int depth, String current)
depth : 재귀사용횟수, 티켓 사용 횟수
current : 현재위치

조건부

재귀 탈출 조건

0. if ( find ) { return; }boolean find : 이동경로를 찾으면 true

• 첫 이동 경로를 찾았다면 모든 재귀함수 return;

usable_ticket함수 자체가 알파벳 순으로 티켓을 정렬하기 때문에 제일 처음 찾은 이동경로가 답이다.

1. if( depth == 총 티켓의 수){ return 지금까지의 이동경로; } - 모든 티켓을 사용한 경우이므로 지금까지의 이동경로를 리턴

2. if( find_next.length == 0) return;

• 현재위치에서 출발하는 티켓이 없으니 모든티켓을 사용할 수 없는 경우이므로 리턴

1. 해당 공항에서 출발하는 티켓들을 찾아 ( usable_tickets 함수 사용 ) 사용한다.

• 이미 사용한 티켓일 경우는 다음 티켓으로 넘어간다.

2. 사용한 티켓은 사용함으로 표시하고 목적지를 현재위치로 depth는 1을 증가시켜서 재귀
   recursive( depth + 1, 티켓의 목적지 )

static void dfs(int depth, String start){
	if(find)return; //0번
	if (depth == tickets.length) { //1번
		final_root = root.clone();
		find = true;
	}
	if( usable_tickets(start).length == 0){ return; } //2번
	String [] next = usable_tickets(start);
	for( int i=0;i<next.length;i++){
		String [] next_info = next[i].split(",");
		if(!is_used[Integer.parseInt(next_info[1])]){
			is_used[Integer.parseInt(next_info[1])] = true;
			root[root_idx++] = next_info[0];
			dfs(depth+1, next_info[0]);
			is_used[Integer.parseInt(next_info[1])] = false;
			root_idx--;
		}
	}
}

usable_tickets 함수

현재 위치에서 출발하는 티켓을 찾아 알파벳이 작은 배열로 반환해주는 함수

선언부

String [] usable_tickets(String current, String [][] tickets)
current : 현재 위치

import java.util.ArrayList;

static String [] usable_tickets(String current, String [][] tickets){
	ArrayList<String> possible = new ArrayList<String>();
	for(int i=0;i<tickets.length;i++){
		if(tickets[i][0].equals(current)){
			possible.add(tickets[i][1]+","+i);
		}
	}
	String [] ret = new String[possible.size()]
	Arrays.sort(possible.toArray(ret));
	return ret;
}

실제 사용할때는 함수가 호출될 때마다 ArrayList가 계속 만들어지기에 클래스변수로 하나를 만들고 호출될 때마다 clear()메소드로 비워서 사용했다

최종코드 ( 프로그래머스)

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    ArrayList<String> finish, tmp;
    String [][] tickets;
    String [] root, final_root;
    int root_idx = 1;
    boolean [] is_used ;
    boolean find;
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        root = new String[tickets.length+1];
        final_root = new String[tickets.length+1];
        is_used = new boolean[tickets.length];
        tmp = new ArrayList<String>(tickets.length);
        root[0] = "ICN";
        dfs(0,root[0]);
        return final_root;
    }
    void dfs(int depth, String start){
        if(find)return;
        if (depth == tickets.length) {
            if(!find){
                final_root = root.clone();
                find = true;
            }
        }
        if( find_next(start).length == 0){ return; }
        String [] next = find_next(start);
        for( int i=0;i<next.length;i++){
            String [] next_info = next[i].split(",");
            if(!is_used[Integer.parseInt(next_info[1])]){
                is_used[Integer.parseInt(next_info[1])] = true;
                root[root_idx++] = next_info[0];
                dfs(depth+1, next_info[0]);
                is_used[Integer.parseInt(next_info[1])] = false;
                root_idx--;
            }
        }
    }

    String [] find_next(String start){
        tmp.clear();
        for(int i=0;i<tickets.length;i++){
            if( tickets[i][0].equals(start)) {
                tmp.add(tickets[i][1] + "," + i);
            }
        }
        String [] arr = new String[tmp.size()];
        Arrays.sort(tmp.toArray(arr));
        return arr;
    }
}

수정한 코드

import java.util.*;
class Solution {
    String ret [], tickets [][];
    HashMap<String, ArrayList<String>> classificaiton = new HashMap<String, ArrayList<String>>(10000);
    ArrayList<String> current_root;
    boolean find, is_used [];
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        for( int i=0;i< tickets.length;i++){
            if(!classificaiton.containsKey(tickets[i][0])){
                classificaiton.put(tickets[i][0],new ArrayList<String>(9999));
            }
            classificaiton.get(tickets[i][0]).add(tickets[i][1]+","+i);
        }
        current_root = new ArrayList<String>(tickets.length);
        current_root.add("ICN");
        is_used = new boolean [tickets.length];
        ret = new String[tickets.length+1];
        recursive(0,current_root.get(0));
        return ret;
    }
    void recursive(int depth, String current){
        //아직 알파벳순으로 제일 빠른 경로를 찾지 못했을 시
        if(!find){
            //depth가 티켓의 갯수와 같을 경우 ret에 current_root를 복사하고 find를 true로
            if (depth == tickets.length) {
                current_root.toArray(ret);
                find = true;
            }
            //next : current에서 출발하는 티켓들을 알파벳순으로 정렬한 배열
            String [] next = find_next(current);
            if( next.length == 0){ return; }
            for(String ticket : next){
                String destination = ticket.split(",")[0];
                int ticket_idx = Integer.parseInt(ticket.split(",")[1]);
                //사용되지 않은 티켓일 경우
                if(!is_used[ticket_idx]){
                    //티켓을 사용하고 current_root에 목적지 추가 후 depth+1하고 목적지를 출발지로 하여 재귀
                    is_used[ticket_idx] = true;
                    current_root.add(destination);
                    recursive(depth+1,destination);
                    //다음 티켓을 사용하기 위해 현재 티켓을 사용안함으로 바꾸고 current_root에서 최근 경로 삭제
                    is_used[ticket_idx] = false;
                    current_root.remove(current_root.size()-1);
                }
            }
        }
    }
    String [] find_next(String start){
        if(classificaiton.containsKey(start)){
            String [] arr = new String[classificaiton.get(start).size()];
            Arrays.sort(classificaiton.get(start).toArray(arr));
            return arr;
        }
        return new String[0];
    }
}