[BFS/DFS] 여행 경로

 

접근

위의 문제는 모든 나열된 경우의 수를 파악해야하기 때문에 1)완전탐색이 필요하고 그래프 형태로 표시할 수 있기때문에 2)DFS로 접근한다. 또한 명확한 최적의 해가 존재하기에 3)BackTracking 기법을 사용한다.

 

 

BFS와 백트래킹 알고리즘 구현시 필요 조건

 

1) BFS의 필요조건

• 최종 출력값
• 방문 여부 확인용 변수
• 현재 노드
• 방문 가능 조건
• 동작
  • 방문 가능하다면 방문.
  • 종료 조건에 도달시 종료 (특정 지점에 도달 및 etc)

 

2) 백트래킹의 필요 조건

 

• 최종 출력값
• 방문 여부 확인용 변수
• 현재 노드
• 방문 가능 조건
• 동작
  •  방문 가능하다면 방문.
  • 조건에 만족되지 않는 경우 되돌아오기. -> 되돌아오는 return값 유형별로 확인하기.
  • 되돌아올때, 방문 여부 확인용 변수와 최종 출력값을 되돌려줘야 한다.

 

구현

• 최종 출력값 : 방문 공항 경로 path
• 방문 여부 확인용 변수 : 티켓 사용 여부 확인용 변수 map<pair<string,string>,int>>
  **동일한 티켓이 두개 이상 있을 수 있음!
• 현재 노드 : 현재 도착한 공항
• 방문 가능 조건 : {현재 도착 공항,방문하려는 공항} 쌍이 존재해야함 && 해당 티켓이 여분이 존재해야함
• 동작
  • 방문 가능시 방문
  • 방문 조건 확인용 변수들 업데이트( 공항경로 & 티켓 사용여부 )
  • 조건에 만족하는 경우, 동작을 끝내기 ( return값을 true로 설정하여 )
  • 조건에 만족하지 않을 경우, 방문 조건 확인용 변수들 롤백

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;

bool dfs(unordered_map<string,vector<string>> graph,map<pair<string,string>,int>& used,vector<string>& path,int ticket_num)
{
    if(path.size()>=ticket_num+1)
    {
        result=path;
        return true;
    }
    
    string cur_city=path.back();

    for(auto city : graph[cur_city])
    {
        if(used[{cur_city,city}]==1) //같은 항공권이 여러장 있을 수 있음.
        {
            used[{cur_city,city}]--;
            path.push_back(city);
            if(dfs(graph,used,path,ticket_num)==true) return true;
            path.pop_back();
            used[{cur_city,city}]++;
        }
    }

    return false;

    /*
    동작 구현
    1) 동작 가능 여부
     - 인접 티켓 확인
     - 사용 가능여부 확인
    */
}

vector<string> solution(vector<vector<string>> tickets)
{
    /*
    1) 출력 (path)
    2) 사용여부 (used)
    3) 노드 (티켓)
    4) 동작
    */
    unordered_map<string,vector<string>> graph;
    map<pair<string,string>,int> used;
    vector<string> path;

    for(auto ticket : tickets)
    {
        graph[ticket[0]].push_back(ticket[1]);
        used[{ticket[0],ticket[1]}]++;
    }

    for(auto& [key , destination] : graph)
    {
        sort(destination.begin(),destination.end());
    }

    path.push_back("ICN");
    dfs(graph,used,path,tickets.size());

    return path;
}

 

 

추가 알게 된 내용

 

1. 직관적인 자료구조 표현법

 

- 특정 도시를 시작으로 하는 티켓들을 나열하는 방법

- 구현 방법: unorderded_map<string,vector<string>>

- 구현 개념: [시작도시][도착도시1,도착도시2]... 로써의 표현 

 

2. 컨테이너 내부 값을 변경해야 할 경우 (& 키워드 사용)

 

for( : )문 사용시, 컨테이너의 내부값은 복사되어진다. 따라서 복사된 값을 변경하여도 실제 컨테이너 내부 값은 변경되지 않는다. 따라서 컨테이너 내부값을 변경하기 위해선 & 키워드를 추가하여 참조하도록 변경해야한다.