반응형
https://school.programmers.co.kr/learn/courses/30/lessons/43164
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
BFS와 DFS 문제 레벨3 단계의 여행경로 문제다.
이해하는 데 확실히 오래 걸린 문제다
처음 생각은 그냥 DFS 문제인 줄 알고 알파벳 정렬 후 빠른 순으로 탐색하였다.
풀면 채점 시 1번 2번 실패, 3번 4번 성공한다.
생각해 낸 아이디어는
위 문구처럼 무조건 다 갈 수 있다는 이야기는
만약 끝까지 탐색 DFS를 했을 경우에도 모든 티켓(간선)을 사용하지 않았다면 그 간선은 마지막에 방문해야 하는 간선이다.
또한 같은 티켓이 두 개일 수 있다.
1. 그래프를 만들며 그래프를 알파벳순으로 정렬한다.
2. 그래프를 순서대로 탐색한다.
3. 더 이상 다른 노드로 이동할 수 없는 경우 사용한 티켓(간선)의 개수와 전체 티켓(간선)의 개수를 체크한다.
3.1달을 경우 이전 노드로 돌아간다.
4 만약 돌아왔으면 다음 2로 돌아가 다음 순서 노드를 탐색한다.
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;
int ticketSize = 0;
vector<string>Aanswer;
bool findAir(string start,int num,vector<string> answer, map<string, map<string, int>, greater<string>>ticketsmap) {
//사용한 티켓 기록
answer.push_back(s.first);
//이동한 간선수와 전체 간선의 수 비교
if (num == ticketSize) { Aanswer = answer; return true; }
//정렬된 간선 순서대로 이동
for (auto s : ticketsmap[start]) {
//간선이 존재하는가 확인
if (s.second >0) {
// 티켓 갯수 빼기
ticketsmap[start][s.first]--;
//재귀함수 실행
if (findAir(s.first, num + 1, answer, ticketsmap) == true)
{
//true 반환시 탈출
return true;
}
else {
//만약 현재 티켓대로 갔을경우 전부 소진하지 못할경우
//티켓을 사용하지 않은 상태로 원복 시킨다
ticketsmap[start][s.first]++;
}
}
}
//간선을 전부 돌았지만 티켓을 전부 사용하지 못했을경우 false 반환
answer.pop_back();
return false;
}
vector<string> solution(vector<vector<string>> tickets) {
string start = "ICN";
map<string, map<string, int>> ticketsmap;
for (int i = 0; i < tickets.size(); ++i)
{
//티켓 그래프 제작
ticketsmap[tickets[i][0]][tickets[i][1]]++;
ticketSize += 1;
}
vector<string> answer = {};
findAir(start,0, answer, ticketsmap);
return Aanswer;
}아래와 같이 확인할수 있다