🌞문제

🌞접근법

조건1. ICN항공에서 출발한다.
조건2. 모든 공항은 알파벳 대뭇자 세글자
조건3. 공항 수는3~10000
조건4. tickets의 [a,b]는 a에서 b로가는 항공편이 있다는 것이다.
조건5. 주어진 항공권은 모두 사용해야 한다.
조건6. 만일 가능한 경로가 2개인 경우 알파벳 순서가 앞서는 경로를 return
조간7. 모든 도시를 방문 할 수 없는 경우는 주어지지 않는다.

구하려는 값 : 방문하는 공항 경로를 배열에 담아서 return

이 문제는 bfs를 이용하면 풀 수 있을 것으로 보인다.
먼저 ICN부터 시작이므로 ICN으로 시작하는 것을 찾는다.
tickets 배열을 for문을 돌면서 ICN으로 시작하는 것을 큐에 추가한다.
큐에서 하나의 요소를 제거하고, 그 경우에 대해서 배열을 돌면서 이동이 가능한 지점을 큐에 추가한다.
이 과정을 통해서 방문을 했다면 visit 배열에 추가한다. visit배열 또한 큐에서 관리를 해주어야 한다.
이렇게 큐를 다 돈다. 결과적으로 bfs를 다돌고나면 큐와 visit에는 모두 방문한 결과만 남아 있게 될 것이다.

그렇다면 이때 큐에 값이 하나만 존재하면 좋겠지만, 그렇지 못하다면 for문을 돌아서 비교를 통하여 알파벳 순서가 앞서는 경로를 찾아야 한다.

🌞풀이

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<vector<string>> tickets;

queue<vector<int>> visit;
queue<int> q;
queue<vector<string>> res;
int cnt = 1;

void bfs()
{
    while(cnt < tickets.size())
    {
        cnt++;
        int x = q.size();
       for(int i=0;i<x;i++)
        {
            vector<int> cur_visit(visit.front());
            visit.pop();
            vector<string> cur_res(res.front());
            res.pop(); 
           
            int idx = q.front();
            q.pop();
            
            for(int j=0; j<tickets.size();j++)
            {
                if(cur_visit[j] == 0 && tickets[j][0] == tickets[idx][1])
                {
                    vector<int> tmp_visit(cur_visit);
                    tmp_visit[j] = 1;
                    visit.push(tmp_visit);
                    q.push(j);
                    
                    vector<string> tmp_res(cur_res);
                    tmp_res.push_back(tickets[j][0]);
                    if(cnt == tickets.size())
                    {
                        tmp_res.push_back(tickets[j][1]);
                    }
                    res.push(tmp_res);
                    
                }
            }
        
        } 
    }

    
}

vector<string> solution(vector<vector<string>> _tickets) {
    tickets = _tickets;
    for(int i=0;i<tickets.size();i++)
    {
        if(tickets[i][0] == "ICN")
        {
            vector<int> v;
            v.resize(tickets.size(),0);
            v[i] = 1;
            visit.push(v);
            q.push(i);
            
            vector<string> reach;
            reach.push_back("ICN");
            res.push(reach);
        }
    }
    
    bfs();
    
    vector<string> answer = res.front();
    res.pop();
    
    while(!res.empty())
    {
        vector<string> oper = res.front();
        res.pop();
        for(int i=0;i<answer.size();i++)
        {
            if(answer[i] != oper[i])
            {
                
                if(answer[i] > oper[i] ) answer = oper;
                break;
            }

        }
    }
    
    return answer;
}