[자바] 프로그래머스 : 여행경로 (DFS 백트래킹) / 접근 방법 및 풀이

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

프로그래머스

Level 3, 정답률 43% 문제입니다.

 

---

실제 코딩테스트에 문제가 나온다면 이런 느낌이지 않을까 싶은 문제입니다.

어느정도 완전탐색에 익숙해지신 분들에게 추천 드리는 문제입니다.

​

모든 코테 문제를 풀 때, 해결 방법을 찾는 방법과 계획법이 중요하다고 생각합니다.

코테에 익숙치 않은 경우 무작정 코드부터 짜는데 이러면 시간은 시간대로 걸리고 테스트 케이스에서 예외가 발생하면 리팩토링이 정말 오래 걸리니 꼭 아래 글처럼 계획을 세우고 문제 푸시는 걸 추천드립니다!

​

​문제 분석

문제에서 tickets[][] 에는 비행기 티켓이 들어가있습니다.

배열을 까보면 순서대로 [출발지점, 도착지점] 이렇게 구성되어있습니다.

​

이 문제의 정답은 이 배열을 가지고 여행 경로를 구하면 됩니다.

모든 첫 여행 시작 지점은 "ICN" 이고, 만약 출발 지점이 두 개 이상이라면 도착지점이 사전 순으로 앞서는 것을 리턴해주면 됩니다.

​

문제의 예시로 설명을 해보겠습니다.

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] 이렇게 배열이 들어온 경우 ICN 부터 시작해야하므로

ICN - JFK - HND - IAD 순서대로 여행을 진행하게 됩니다.

​

[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] 이런 경우라면

ICN - ATL - ICN - SFO - ATL - SFO 입니다.

이 경우는 ICN이 두 개라서 사전 순으로 앞 서는 것부터 진행해주면 됩니다.

​

 

문제 접근 방법 및 풀이 도출

위에 처럼 문제를 분석했다면, 어떤식으로 문제를 풀지 생각을 해봐야합니다.

​

저 같은 경우는

1. 먼저 문제를 이해한다.

2. 예외 경우를 생각한다.

3. 어떻게 풀지 알고리즘 및 방법을 생각한다.

3. 풀이한다.

​

보통 이 순서로 진행을 하는데, 위에서 1번의 경우를 다뤘으니 2번 예외 경우를 생각해봐야합니다.

​

만약에 [["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]] 이렇게 경우가 들어왔을 경우

사전순대로 진행을 했을 때 막히는 부분이 있을 수 있습니다.

ICN - A - B - D (사전 순대로 진행해서 막히는 예외상황)

ICN - A - C - A - B - D (사전 순대로 처리를 하지 않았지만, 비행기 티켓을 모두 이용한 경우)

​

이렇게 두 가지 경우가 나오게 되는데 밑에 경우가 정답이 되어야합니다.

​

​

이 예외 상황을 고려하지 않았을 경우에 단순 문제에 주어진 조건만 보고 HashMap으로 풀 수도 있게됩니다.

HashMap으로도 풀 수야 있겠지만, 비행기 티켓을 모두 사용하기는 힘들겠죠?

​

따라서 저는 이 문제를 풀기 위해서, 완전탐색을 진행 한 후 정렬해서 사전 순으로 가장 빠른 것을 정답으로 리턴해주게 문제를 풀었습니다.

 

 

문제 해결

이제 어떻게 문제를 풀지도 계획 했으니 문제 풀이를 위한 순서를 정해야합니다.

​

먼저 우리는 완전탐색 dfs (백트래킹)을 이용해서 푼다고 위에서 정했습니다.

 

1. 완전탐색을 통해 가능한 모든 경로를 구한다.

2. 정렬을 한다.

3. 가장 첫 번째 요소를 리턴해준다.

​

이 순서대로 풀어보겠습니다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
    private static boolean[] visited; // 방문한지 안한지를 체크하는 visited 배열
    private static List<String> result = new ArrayList<>();

    public static String[] solution(String[][] tickets) {
        // 1. 변수 세팅
        visited = new boolean[tickets.length];

        // 2. 완전탐색 및 정렬
        dfs(0, "ICN", "ICN", tickets);
        Collections.sort(result);

        // 3. 정답 출력
        String[] answer = result.get(0).split(" ");
        return answer;
    }

    public static void dfs(int idx, String start, String route, String[][] tickets) {
        // 1. 탈출 조건 (비행기 티켓을 모두 사용한 경우)
        if (idx == tickets.length) {
            result.add(route);
            return;
        }

        // 2. 백트래킹 알고리즘 사용
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(start) && !visited[i]) {
                visited[i] = true;
                dfs(idx + 1, tickets[i][1], route + " " + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
        return;
    }
}

위와 같이 풀면 모든 테스트 케이스에 대해 통과를 할 수 있습니다.

​

백트래킹이 익숙하지 않은 분들은 아래 문제 풀면서 익숙해지시는 걸 추천드리겠습니다.

피로도 문제 상위호환 느낌이 여행경로 문제라고 생각합니다~

 

https://blog.naver.com/sosow0212/222928157422

[자바] 프로그래머스 - 피로도 / 백트래킹 알고리즘 정복하기