▶문제설명
코딩테스트 연습 > 깊이/너비 우선 탐색 > 여행경로
▶ 설계
재귀 함수를 잘 구현하면 해결할 수 있을 것 같다.
재귀 함수의 종료 조건은 모든 티켓을 다 사용했을 경우이다.
전역변수 N에 티켓의 개수를 저장하자.
1 2 3 4 5 6 7 8 | bool findPath(vector<string>& answer, vector<vector<string>> tickets, string city, int cnt) { if(N==cnt) return true; return false; } | cs |
문제에서 경로가 여러개인 경우 사전순으로 빠른 경로를 출력하라고 했으므로 sort(tickets.begin(), tickets.end())를 호출해서 정렬해주면 문제 해결이 더 쉬울 것으로 보인다.
사용된 티켓을 또 사용할 수 없으므로 bool usedTickets[10000]을 선언해서 체크하자.
티켓을 순차적으로 보면서 가능한 모든 경우를 일일이 확인해보자.
▶ 구현
문제에서 "ICN"에서부터 출발한다고 했으므로 findPath()를 호출하기 전에 answer.push_back("ICN")를 호출해주었다.
이미 티켓이 사전순으로 정렬되어 있으므로 tickets를 처음부터 훑으면서 출발지가 city와 일치하는 경우를 찾아가며 answer.push_back("도착지")해 나가다가 N==cnt가 되었을 때 종료하도록 구현했다.
재귀함수가 bool타입을 반환하도록 하여 정답을 찾고 나면 true를 리턴하고 더이상 진행되지 않도록 했다.
그리고 모든 경우를 해보아야 하므로(브루트 포스) 다음 티켓을 찾기 전에 answer.pop()해서 원래의 상태로 되돌려주었다.
▶Solution
'■ 알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 소수 찾기 (0) | 2019.12.14 |
|---|---|
| [프로그래머스] 다리를 지나는 트럭 (0) | 2019.12.13 |
| [프로그래머스] 기능개발 (0) | 2019.12.12 |
| [프로그래머스] 땅따먹기 (0) | 2019.01.03 |
| [프로그래머스] 완주하지 못한 선수 (0) | 2018.12.29 |