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

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

프로그래머스

 

문제 설명

공항 ICN에서 출발해서 모든 노드들을 들려야 한다. 그리고 모든 티켓을 사용해야 한다. 

ICN에서 출발해서 JFK -> HND -> IAD 이렇게 하면 모든 티켓을 사용할 수 있다. 이때 가능한 경로가 2개라면 알파벳 순서가 앞서는 경로를 return 한다. 

 

문제에 대한 아이디어

• String으로 되어 있는 각 노드들을 Integer로 바꿔 주어야 한다
• ticket을 알파벳 순서대로 번호를 매겨주어야 한다.

 

이제 중요한 것은 그래프를 어떻게 구현해줘야 하는지이다. 지금 까지는 무조건 ArrayList 배열을 만들어 인접 리스트 형태로 구현해서 풀었었다. 인접 행렬 방법을 쓰는 것은 플로이드 와샬 알고리즘 말고는 사용한 적이 없었다. 이 문제를 풀면서 visited를 어떻게 해야 할까 고민하다가 질문하기를 보니 인접 행렬로 구현해서 방문했으면 1을 0으로 바꾸는 식으로 구현한 것을 보았다. 알고 있으면 자주 사용할거 같아 그 방법으로 풀어보았다. (단, 여기는 공항수가 10000개 이하라 가능한 것 같다)

 

• 방문했으면 2차원 배열을 -=1
• 임의의 리스트를 만들어 지금 현재 방문한 노드들을 모두 집어 넣는다
• 그 후 다음 방문할 노드를 집어 넣는다. 그리고 DFS 탐색

이렇게 하면 문제는 DFS로 모든 방법을 탐색할 수 없다는 것이다. 그래서 백트래킹을 이용해 리턴 한 곳은 다시 +=1을 해주었다.

• 만약 모든 ticket을 사용했다면 임의의 배열에 현재 list에 있는 모든 것을 집어 넣는다.

이유는 똑같은 ticket이 존재하기 때문이다.

 

코드로 설명

import java.util.*;

class Solution {
    List<Integer> list = new ArrayList<>();
    int ticket_count = 0;
    public String[] solution(String[][] tickets){
        Map<String, Integer> map = new HashMap<>(); //Index(String -> Integer)
        Map<Integer, String> mp = new HashMap<>();  //Index(Integer -> String)
        List<String> ticketList = new ArrayList<>();
        
        //ticketList 같은 것은 삭제
        for(int i = 0; i<tickets.length; ++i){
            for(int j = 0; j < 2; ++j){
                if(!ticketList.contains(tickets[i][j])){
                    ticketList.add(tickets[i][j]);
                }
            }
        }
        
        ticket_count = tickets.length;
        Collections.sort(ticketList);
        for(int i = 0; i<ticketList.size(); i++) {
            map.put(ticketList.get(i), i);
            mp.put(i, ticketList.get(i));
        }
        
        //인접 행렬 그래프
        int[][] arr = new int[ticketList.size()][ticketList.size()];
        for(int i = 0; i<tickets.length; ++i){
            int start = map.get(tickets[i][0]);
            int end = map.get(tickets[i][1]);
            arr[start][end] += 1;
        }
         
        boolean[][] visited = new boolean[ticketList.size()][ticketList.size()];
        int start = map.get("ICN");
        list.add(start);
        dfs(arr, visited, start, 0);
        String[] answer = new String[list2.size()];
        for(int i = 0; i<list2.size(); ++i){
            answer[i] = mp.get(list2.get(i));
        }
        return answer;
    }
    
    List<Integer> list2 = new ArrayList<>();
    public void dfs(int[][] arr, boolean[][] visited, int start, int ticket_count){
        //모든 ticket을 사용했거나 처음 모든 방문 완료
        if(ticket_count == this.ticket_count  && list2.size() == 0){
            list2 = new ArrayList<>();
             for (Integer integer : list) {
                list2.add(integer);
            }
            return;
        }
        
        for(int i = 0; i<arr[start].length; i++){
            if(arr[start][i] >= 1){
                arr[start][i] -= 1;
                List<Integer> list1 = new ArrayList<>(list); //현재까지 방문한 노드
                list.add(i); //다음 방문할 노드 추가
                dfs(arr,visited, i, ticket_count+1);
                arr[start][i] += 1; //백트래킹
                list = new ArrayList<>();
                list.addAll(list1); //바로 전에 방문했던 노드는 뺀다. 방향이 아니라 return 한 것이므로
            }
        }
    }
}