뚝딱뚝딱

여행 경로

💡문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.


주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

딱 보자마자 모든 경로를 탐색해야 하기 때문에, dfs를 사용해야 한다는 점은 알아야 한다.

그런데, 문제를 보면, 여러개의 경로가 나올 시 사전 순으로 앞서는 경로를 return해야 한다.

여러개의 경로를 구해두고 그 중에서 알파벳 순으로 먼저인 경로가 앞으로 오도록 정렬한 후 맨 앞에 있는 것을 선택해야한다.

따라서 이 문제는 BFS도 적용해야 한다.(위에서 말한 바와 같이 정렬만 하면 되긴 한다)

다음과 같은 단계로 진행할 수 있다.

1. 여러가지 경로 자체를 리스트 형태로 여러개 저장할 수 있는 이중 리스트를 생성하자.

static List<List<String>> answerList;

솔루션 함수 밖에서 생성해주었다.

2. 방문 여부를 위한 boolean타입 배열을 선언하자.

static boolean[] visited;

이 역시 솔루션 함수 밖에서 생성해주었다.

3. 이제 이중리스트에 ArrayList로 동적 할당해주고, 방문 배열 역시 tickets배열 크기만큼 동적 할당하자.

answerList = new ArrayList<>();
visited = new boolean[tickets.length];

솔루션 함수 내로 들어왔다.

4. 이제 tickets 배열을 순회하면서 출발지가 "ICN"인지 확인하자.

for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {

5. 조건에 만족한다면, 경로를 저장하기 위한 list를 생성하고 동적할당한다. 그리고 출발지인 "ICN"을 담는다.

현재 노드를 방문한 것이므로 visited[i]를 true로 하고, 리스트에는 해당 노드의 도착지를 저장한다.

List<String> list = new ArrayList<>();
list.add("ICN");
visited[i] = true;
list.add(tickets[i][1]);

6. 도착지인 tickets[i][1]이 다시 출발지가 되어 다음 노드를 방문해야 한다. 따라서 아직 방문하지 않은 노드들 중 출발지가 tickets[i][1]인 노드를 찾아 위의 과정을 반복하자. 이를 dfs함수에 구현하자.

public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }

   - dfs함수는 tickets와 출발지 인덱스, 진행중이던 경로 list에 대한 정보를 받는다.

   - 만약 현재 list의 크기가 tickets의 길이보다 1 큰 것과 같다면, 모든 tickets를 고려한 것이기 때문에, 이중 리스트인 answerList에 list를 넣는다. = 경로 모음집에 경로를 하나 추가한 것이다.

   - 아직 tickets를 다 방문하지 않았다면, 모든 노드에 대해서, 아직 방문하지 않았고, 인자로 받은 출발지를 갖는 노드를 방문한다.

   - 역시 list에 방문한 노드의 도착지를 넣어준다 (출발지는 이전 단계에서의 도착지로, 이미 넣어졌기 때문이다)

   - 그리고 그 도착지를 기점으로 다시 dfs를 호출해서 반복되도록 해준다.

   - 다 돌고 나서 다시 다른 경로를 순회하기 위해 다시 visited[i]를 false로 바꾸어주는 단계를 잊어선 안된다.

   - 동일한 원리로 list에서도 제거해준다.

7. 다시 solution함수로 돌아오자. 방금 전까지 dfs가 어떻게 돌아가는지를 확인하였다. 이 dfs를 최초로 불러주자.

dfs(tickets, i, list);
visited[i] = false;

   - 여기에서도 dfs를 돌고난 후 혹시 다른 경로를 먼저 방문했을 시를 고려해서 visited[i]를 false로 바꿔주는 것을 잊지 말자.

8. 이렇게 가능한 경로를 다 구했으면, List에 들어있는 경로들을 알파벳 순으로 정렬해주자.

Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
});

   - Collections의 sort함수를 사용할건데, 람다식을 이용해서 모든 경로에 대해 각각의 첫번째부터 끝번째 노드까지 알파벳 순을 비교해서 빠른것이 앞으로 오도록 설계한다.

9. 이제 answerList의 맨 첫번째 경로가 asnwer가 될 것이다. 이 경로 하나를 가져오기 위해 answer를 list로 선언하고 answerList의 0번째 리스트를 가져와 할당한다. 그리고 list의 toArray함수를 통해 answer를 배열 형태로 반환하도록 한다.

List<String> answer = answerList.get(0);

return answer.toArray(new String[answer.size()]);

이렇게 해서 모든 경로를 탐색하고, 정렬을 통해 알파벳 순으로 가장 빠른 경로를 찾아낼 수 있었다.

전체 코드는 아래와 같다.

import java.util.*;

class Solution {
    static List<List<String>> answerList;
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        answerList = new ArrayList<>();
        visited = new boolean[tickets.length];
        
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {
                List<String> list = new ArrayList<>();
                list.add("ICN");
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
            }
        }
        
        // 결과로 반환할 경로 선택 (알파벳 순서가 앞서는 경로)
        Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
        });

        List<String> answer = answerList.get(0);

        return answer.toArray(new String[answer.size()]);
    }
    
    public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }
}

이제 DFS문제를 3-4번 풀어보니, 어느정도 감이오고, 문제를 읽어보면 DFS로 풀어야하는지 알 수 있게 되었다.

확실히 BFS보다 DFS의 비중이 더 많은 것 같기도 하다.

그리고 자바 문법은 더 꼼꼼히 살펴보아야겠다!!