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

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 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(); visited = new boolean[tickets.length]; //티켓 사용 여부 backtracking("ICN",0,"ICN", tickets); Collections.sort(routes); String[] ret = routes.get(0).split(" "); return ret; } }

[배운점]

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

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

백트래킹의 기본 원리

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

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

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

반응형

from http://sw-potato.tistory.com/103 by ccl(A) rewrite - 2021-08-04 18:26:18