JAVA 프로그래머스 Lv.3 여행경로

 

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

 

---

문제

1. 입력으로 항공권 정보가 담긴 2차원 배열 tickets가 들어옴.
2. 공항의 수는 ( 3 <= 공항의 수 <= 10000 ).
3. tickets의 각 행  [a, b] 는 a 공항에서 b 공항으로 가는 항공권이 있음을 뜻함.
4. 주어진 항공권은 모두 사용해야 됨.
5. 가능한 경로가 2개 이상이라면 알파벳 순서 오름차순으로 정렬하여 가장 처음 것을 return.

---

 

 

 

초기 코드

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
    	String[] answer = {};

        Arrays.sort(tickets, (o1, o2) -> o1[1].compareTo(o2[1]));

        LinkedList<String[]> list = new LinkedList<>(Arrays.asList(tickets));

        ArrayList<String> temp = new ArrayList<>();

        
        while (!list.isEmpty()) {
            for (int i = 0; i < list.size(); i++) {
                String[] str = list.get(i);
                if (temp.isEmpty() && str[0].equals("ICN")) {
                    temp.add(str[0]);
                    temp.add(str[1]);
                    list.remove(i);
                    break;
                }
                if (!temp.isEmpty() &&temp.get(temp.size()-1).equals(str[0])) {
                    temp.add(str[1]);
                    list.remove(i);
                    break;
                }
            }
        }

        answer = temp.toArray(new String[0]);
        
        return answer;
    }
}

 

일단 원하는 결과를 얻어보기 위해 되는대로 만들어본 코드.

tickets 배열의 1번째 열을 오름차순 정렬하여 경로가 2개 이상일 경우의 조건에 만족할 수 있도록 하였다.

list에 정렬한 tickets 배열의 데이터를 모두 추가하여 연결리스트 list로 추가, 삭제가 가능하도록 했다.

list에서 조건에 맞는 데이터들을 temp에 추가하며 다 쓴 데이터는 remove하여 중복되지 않도록 한다.

list 배열이 완전히 빌 때까지 반복하여 temp 배열에 순서대로 갈 수 있는 곳을 추가한다.

 

수정한 코드

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        Arrays.sort(tickets, (o1, o2) -> o1[1].compareTo(o2[1]));

        LinkedList<String[]> list = new LinkedList<>(Arrays.asList(tickets));

        ArrayList<String> temp = new ArrayList<>();

        for (int i = 0; i < list.size(); i++) {
            String[] str = list.get(i);
            if (str[0].equals("ICN")) {
                temp.add(str[0]);
                temp.add(str[1]);
                list.remove(i);
                break;
            }
        }
        
        while (!list.isEmpty()) {
            for (int i = 0; i < list.size(); i++) {
                String[] str = list.get(i);
                if (temp.get(temp.size() - 1).equals(str[0])) {
                    temp.add(str[1]);
                    list.remove(i);
                    break;
                }
            }
        }

        answer = temp.toArray(new String[0]);
        
        return answer;
    }
}

 

기존 코드가 시간초과가 나서 얼마나 줄여야 될지 모르겠지만 조금 바꿔봤다.

while문 안에 처음 추가해야 되는 공항의 조건문이 있어 혹시 계속 거쳐 가서 느려지나 싶어 while문 밖으로 꺼내봤다.

 

결과는 똑같았으므로 이 방법 말고 다른 방법을 찾아야 된다.

 

다시 보니 깊이/넓이 우선 탐색 항목에 있는 문제였다.

 

dfs로 푸는게 좋을 것 같다.

 

최종 코드

import java.util.*;

class Solution {
    public static boolean[] visited;
    public static ArrayList<String> route;

    public static void dfs(String depart, String arrive, String[][] tickets, int count) {
        if (count == tickets.length) {
            route.add(arrive);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (depart.equals(tickets[i][0]) && !visited[i]) {
                visited[i] = true;
                dfs(tickets[i][1], arrive + " " + tickets[i][1], tickets, count + 1);
                visited[i] = false;
            }
        }
    }
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        visited = new boolean[tickets.length];
        route = new ArrayList<>();

        dfs("ICN", "ICN", tickets, 0);

        Collections.sort(route);

        answer = route.get(0).split(" ");
        
        return answer;
    }
}

 

dfs나 bfs는 잘 몰라서 다른 분들이 만든 것을 참고했다.

 

dfs의 for 반복문 부분은 내가 만든 것에서 수정을 했는데 visited 배열에서 변경한 부분을 다시 false상태로 바꿔야 된다는 것이 가장 이해하기 어려웠다.

내가 이해하기로는 해당 함수가 재귀함수로 사용되고 있기 때문에 해당 반복문의 visited를 true로 만든 후 재귀 함수 부분이 실행되기 때문에 사용한 항공권은 true로 변한 상태에서 재귀 함수로 넘어가게 되는 것 같다.

이후 마지막으로 실행된 재귀 함수가 끝나며 count가 최대로 증가된 상태에서 함수의 초기 조건문인 if문을 거친 후 false 부분을 실행하여 다시 초기 상태의 visited 배열로 돌아가게 된다.

 

for 반복문을 통해 tickets.length 만큼 실행되어 모든 항공권이 사용된다면(count와 tickets.length가 같을 때) 함수 초반 부분에 있는 if문을 통해 모든 루트가 완성된 만큼 arraylist에 저장이 된다.

 

visited[i] = true;					visited
dfs(tickets[i][1], arrive + " " + tickets[i][1], tickets, count + 1);					1
	visited[i] = true;
	dfs(tickets[i][1], arrive + " " + tickets[i][1], tickets, count + 1);				2
		visited[i] = true;
		dfs(tickets[i][1], arrive + " " + tickets[i][1], tickets, count + 1);			3
		visited[i] = false;			3
	visited[i] = false;				2
visited[i] = false;					1

 

표로 대충 구조를 만들어봤다.

이런 방식으로 만들어져 재귀 함수 내에서는 변화된 배열로 사용되게 하고 재귀가 끝난 이후에는 초기 배열로 돌아가게 해 다시 사용이 가능하도록 만든 것 같다.

 

이 구조를 이해하기 전에는 route(ArrayList)를 그냥 문자열로 받아도 되지 않나 했는데,

이해하고 다시 보니 for 반복문을 통해 가능한 루트를 여러 번 받아 저장한다는 것을 알게 됐다.

이후에 main 함수에서 Collections.sort 메서드로 route 배열을 정렬하여 알파벳 순서가 가장 빠른 것을 출력하여 원하는 결과를 출력한다.

여기서는 문자열을 받아 배열에 추가하여 오름차순으로 정렬한 것 중 가장 앞의 것을 출력한다는 것이 주요한 내용인 것 같다.

 

 

 

 

dfs나 bfs 알고리즘을 사용하는 문제들은 내가 많이 안 풀어보기도 했고 너무 어려워서 손을 안 대게 됐는데 앞으로 많이 풀어봐야 될 것 같다...

 

이 알고리즘이랑 dp가 제일 어려운 것 같다.

머리에 쥐가 난다.