TIL - 2021-08-03 알고리즘 풀이(여행경로)

프로그래머스 Level 3 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164?language=java

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

 

[접근방식 (틀림)]

문제에 대한 이해가 부족에 초기 접근이 잘못되었던 것 같다

 

- 모든 경로를 순회해야하는 문제로 dfs/bfs 를 적용하면 될 것으로 판단

- ArrayList인 graph와 visited 배열에 인덱스 접근을 하기 위해 맵(Map)을 사용해 공항(key) - 값(value)를 할당

- 이후 bfs에서 PriorityQueue를 활용해 공항 중 사전순이 가장 빠른 것을 뽑아 순회

 

결과

주어진 티켓을 모두 사용해야한다는 조건이 있어 갔던 공항도 다시 가야하는 경우가 발생

원하는 결과값이 나올 수 없었음

또한 쓸데없이 너무 많은 자료구조를 사용한 것 같아 비효율적이었던 것 같다...

더 생각을 해서 접근!

       

[풀이]

2시간 가량 고민한 결과 다른 사람들의 코드를 참고하기로 결정

- backtracking 방식을 사용하면서 순회
- 아직 사용하지 않은 티켓이고, 현재 공항이 출발지인 티켓인 경우 현재까지 경로(route) + " " + 도착지 형태로 추가

- 순회하면서 모든 티켓이 사용된 경우(cnt == tickets.length) 이 때의 경로(route)를 routes에 저장
- 가능한 모든 경로를 찾은 후 저장되어있던 routes 리스트를 정렬해 사전순으로 가장 빠른 경로를 찾는다

 

import java.util.*;

class Solution {

    ArrayList<String> routes;
    boolean[] visited;

    public void backtracking(String cur, int cnt, String route, String[][] tickets){
        if(cnt == tickets.length){
            routes.add(route);
            return;
        }
        for(int i=0;i<tickets.length; i++){
            if(visited[i]==false && tickets[i][0].equals(cur)){
                visited[i]=true;
                backtracking(tickets[i][1], cnt+1, route+ " " + tickets[i][1], tickets);
                visited[i]=false;
            }
        }
    }

    public String[] solution(String[][] tickets) {
        routes = new ArrayList<>();
        visited = new boolean[tickets.length]; //티켓 사용 여부

        backtracking("ICN",0,"ICN", tickets);
        Collections.sort(routes);
        String[] ret = routes.get(0).split(" ");
        return ret;
    }
}

 

[배운점]

정렬이 가장 빠른 순서를 찾는 경우 문자열로 계속 담아가면서 마지막에 정렬한번으로 해당 결과들을 정렬한 후

0번 인덱스의 값을 반환하는 방식을 배울 수 있었다.

 

백트래킹의 기본 원리

- 어떤 노드의 유망성(가능성)을 검증한 후,

  유망한 노드인 경우 해당 노드를 탐색, 유망하지 않은 경우 해당 노드를 배제하고 다른 자손을 탐색

- 유망하지 않은 노드를 배제하기 때문에 풀이 시간이 단축된다.