프로그래머스 - (Java)여행경로

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

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

1. 유형

DFS

 

2. 시뮬레이션

로직

1. Map<String, List> 형태로 자료구조 사용
2. DFS사용하여 완전 탐색

3. 코드

풀이1

import java.util.*;
class Solution {
    static int N;
    static List<String> ret;
    static public String[] solution(String[][] tickets) {
        String[] answer = {};
        N = tickets.length;
        List<String> list;
        ret = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for(String[] ticket: tickets){
            String start = ticket[0];
            String end = ticket[1];
            if(map.containsKey(start)){
                list = map.get(start);
            }else{
                list = new ArrayList<>();
            }
            list.add(end);
            map.put(start, list);
        }
        dfs(0, map, "ICN", "ICN");
        Collections.sort(ret);
        answer = ret.get(0).split("\\|");
        return answer;
    }
    static void dfs(int depth, Map<String, List<String>> map, String port, String str){
        if(depth == N){
            ret.add(str);
            return;
        }
        List<String> temp = new ArrayList<>();
        if(!map.containsKey(port)) return;
        temp.addAll(map.get(port));
        for(String listvalue: temp){
            List<String> list = map.get(port);
            list.remove(listvalue);
            map.put(port, list);
            dfs(depth+1, map, listvalue, str+"|"+listvalue);
            list.add(listvalue);
            map.put(port, list);
        }
    }
}

// 1. map {문자열, 리스트} 형식
// 2. dfs(맵, 뎁스, 공항):
//     기저조건
//     리스트 탐색

 

풀이2

조금더 쉬운 풀이. 재귀를 호출 할때마다, tickets의 처음부터 끝까지 visited 배열 사용하여, 전부 판단하는 것.

import java.util.*;
class Solution {
    static List<String> list;
    public String[] solution(String[][] tickets) {
        list = new ArrayList<>();
        boolean visited[] = new boolean[tickets.length];
        dfs(tickets, 0, "ICN", "ICN",visited);
        Collections.sort(list);
        String[] answer = list.get(0).split(",");
        return answer;
    }
    
    static void dfs(String[][] tickets, int depth, String port, String str, boolean visited[]){
        if(depth == tickets.length){
            list.add(str);
            return;
        }
        for(int i=0; i<tickets.length; i++){
            if(!visited[i] && tickets[i][0].equals(port)){
                visited[i] = true;
                dfs(tickets, depth+1, tickets[i][1], str+","+tickets[i][1], visited);
                visited[i] = false;
            }
        }
    }
}