[고득점Kit][DFS] 여행 경로 ⭐⭐⭐

[DFS] 여행 경로

난이도 ⭐⭐⭐

문제

내 풀이 ⭕

DFS에 관해 배운게 많았던 문제라고 생각함! 프로그래머스의 질문하기에 올려주신 다른 분들의 테스트 케이스가 도움 많이 되었다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(vector<string> a, vector<string> b)
{
	if (a[0] == b[0])
		return a[1] < b[1];
	return a[0] < b[0];
}

bool DFS(vector<vector<string>> tickets, vector<string>& answer, vector<bool> usedTickets, string start, int depth)
{
    if (depth == usedTickets.size())
        return true;
    
	for (int i = 0; i < tickets.size(); i++)
	{
		if (tickets[i][0] == start && !usedTickets[i])
		{
			usedTickets[i] = true;
			answer.push_back(tickets[i][1]);
            if (DFS(tickets, answer, usedTickets, tickets[i][1], depth + 1))
			    return true;
            usedTickets[i] = false;
		}
	}
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) 
{
    sort(tickets.begin(), tickets.end(), compare);
         
    vector<string> answer;
    answer.push_back("ICN");
    vector<bool> usedTickets(tickets.size());
    
    DFS(tickets, answer, usedTickets, "ICN", 0);
    
    return answer;
}

✨DFS✨ 이 문제의 포인트

1. 모든 항공권을 한번에 다 사용하는게 가능하며 또 모든 항공권을 전부 다 사용 해야 한다.
   • 따라서 아직 항공권을 다 쓰지도 못했는데 막혔다면, 빠꾸해야 한다. 테스트 케이스 [[ICN, A], [ICN, B], [B, ICN]] 같은 경우, 아직 항공권 다 쓰지도 못했는데 ICN - A 항공권을 사용하려는 경우엔, A 에서 출발하는 항공권이 없기 때문에 다시 A 방문을 취소하고 빠꾸해야 한다.
   • 재귀의 종료 조건은
2. 재귀단계 마다 answer에 해당 방문 도시를 저장해놔야 하며, 빠꾸하고 방문 취소해야 하는 경우도 생길 수 있다.
3. 모든 티켓을 다 쓰고 모든 도시를 방문하는데에 성공했다면 더 이상 또 다른 조건의 재귀 함수를 호출하지 않고, 즉 또 다른 경로가 있나 볼 필요 없이 그냥 모든 과정을 다 끝내야만 한다.
   • 따라서 DFS 함수를 bool 타입으로 하여 성공 여부를 받았고 성공했다면 return하여 for 문 내에서 더 이상 다음 도시를 살펴보지 않고 그냥 전부 빠져나오도록 한다.
   • 이 과정이 없다면 모든 도시를 다 방문했음에도 불구하고 빠져나오는 과정에서 다음 for문 반복을 돌기 때문에 answer에 계~속 경로들이 추가로 저장된다.
4. 방문 도시는 중복이 될 수 있다. ICN 👉 A 👉 ICN 가능. 항공권 중복 사용이 안되는 것 뿐! 항공권은 일회성.

• 재귀 종료 조건
  • 모든 항공권을 다 씀 if (depth == usedTickets.size())
    • 👉 성공! true 리턴
  • 모든 항공권을 다 쓰지도 않았고 (if (depth == usedTickets.size()) 에 걸리지 않음) 더 이상 갈 수 있는 곳도 없다면 (for문 다 돌 때까지 if(DFS) return true 를 만나지 못 함)
    • 👉 실패! false 리턴
    • 또한 방금 방문한 도시로서 temp에 추가했었던 도시를 삭제해야 한다.

bool compare(vector<string> a, vector<string> b)
{
	if (a[0] == b[0])
		return a[1] < b[1];
	return a[0] < b[0];
}

sort(tickets.begin(), tickets.end(), compare);

같은 도시라면 알파벳 순서가 더 앞서는 도착 도시를 가진 항공권을 선택해야 하므로 알파벳 순서대로 tickets를 오름차순 정렬한다. 같은 도시라면 도착지에 따라 정렬하도록 한다.

    vector<string> answer;
    answer.push_back("ICN");
    vector<bool> usedTickets(tickets.size());
    
    DFS(tickets, answer, usedTickets, temp, "ICN", 0);

    bool DFS(vector<vector<string>> tickets, vector<string>& answer, vector<bool> usedTickets, string start, int depth)
    {

• 경로는 temp에 저장하고 최종적으로 모든 항공권을 다 쓴 것이 확인 되었을 때 answer에 temp를 복사할 것이다.
  • temp에 미리 시작 도시인 “ICN”을 넣어 둔다.
• usedTickets 👉 사용한 항공권은 True 체크 표시 한다.
• DFS 의 각각 재귀 단계는 현재 항공권을 통해 방문 중인 도시와 같다.
• DFS 함수 매개 변수
  • tickets 항공권들
  • answer 경로를 저장할 벡터. solution 함수 내에서 실행한 최초의 DFS 함수 실행이 끝난 후 경로들이 answer에 반영 되야 하므로 참조로 넘긴다.
    • 함수 종료 후에도 남아야 하므로 참조로 넘김
  • usedTickets 사용한 항공권 체크. tickets와 사이즈 같음.
    • 참조로 넘기지 않는다. 도시 방문 경로마다, 즉 각각 다른 재귀 함수들마다 항공권 사용 순서라던가 사용 상태는 달라야 한다.
  • start 현재 방문 중인 도시
    • for문으로 tickets를 살피며 start에서 출발하며 아직 안 쓴 항공권을 찾아야 한다.

    if (depth == usedTickets.size())
        return true;

성공 종료 조건은 이렇다. 항공권 다 썼다면 성공이므로 true를 리턴하고 깊이 탐색을 끝낸다.

	for (int i = 0; i < tickets.size(); i++)
	{
		if (tickets[i][0] == start && !usedTickets[i])
		{
			usedTickets[i] = true;
			answer.push_back(tickets[i][1]);
            if (DFS(tickets, answer, usedTickets, tickets[i][1], depth + 1))
			    return true;
            usedTickets[i] = false;
		}
	}
    answer.pop_back();
    return false;

• 실패 종료 조건은 현재의 방문 경로에서 현재 해당 항공권을 사용하면 모든 항공권을 다 사용할 수가 없는 경우이다.
  • for문을 다 돌면서 티켓을 살펴 봐도 이 도시에서 갈 수 있는 항공권이 없거나
  • 있더라도 DFS 가 성공적으로 true 를 리턴해준 경우가 없었다면
  • 즉 if(DFS) return true 를 한번도 만나지 못했다면 현재의 그 도시는 answer.pop_back() 방문을 취소하고 false를 리턴해야 한다.
• 모든 항공권을 다 사용하는데에 성공했다면 더 이상 for 문 다른 반복을 돌지 않고 전부 다 끝내야 한다. return true. 이 과정이 없다면 모든 항공권을 다 사용했는데도 불구하고 빠꾸하면서 또 다른 항공권을 또 써서 방문하게 된다.
  • usedTickets는 참조가 아니기 때문에 빠꾸하면 다시 이전 재귀 단계의 상태로 리셋 될 테니까 방문이 가능해짐
  • 따라서 아예 더 이상 다른 경로의 깊이 탐색을 못하도록 빠져 나와야 한다.
• 해당 항공권을 지금 썼을 때, 모든 항공권을 다 쓰는데에 실패하게 된다면, 그래서 if(DFS) return true 에 해당 되지 않았다면
  • usedTickets[i] = false 이 항공권은 추후 알맞는 경우에 다시 사용을 해야 하기 때문에 다시 false 로 바꿔준다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기