[C++] 프로그래머스 여행경로 DFS/BFS

1번채점 오답이 자꾸나온다.

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

using namespace std;

vector<string> DFS(string start, vector<vector<string>> tickets);

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer = DFS("ICN", tickets);
    
    return answer;
}

vector<string> DFS(string start, vector<vector<string>> tickets)
{
    vector<string> result;
    bool visited[10000];
    int ticketCount = 0;
        
    sort(tickets.begin(), tickets.end());
    
    //priority_queue<string, vector<string>, greater<string>> pq;
    //pq.push("ICN");
    
    queue<string> q;
    q.push("ICN");
    
    
    //while(!pq.empty())
    while(!q.empty())
    {
        //string currNode = pq.top();
        string currNode = q.front();
        //pq.pop();
        q.pop();
        result.push_back(currNode);
        
        for(int i = 0; i < tickets.size(); i++)
        {
            string prevNode = tickets[i][0];
            string nextNode = tickets[i][1];
            
            if(visited[i] == true) continue;
            
            if(currNode == prevNode && visited[i] == false)
            {
                visited[i] = true;
                int counts = 0;
                
                for(int j = 0; j < tickets.size(); j++)
                {
                    string tempPrevNode = tickets[j][0];
                    string tempNextNode = tickets[j][1];
                    
                    if(visited[j] == true) continue;
                    
                    if(nextNode == tempPrevNode && visited[j] == false) //다음 갈 경우의 수가 있나
                    {
                        counts++;
                    }
                }
                
                if(counts > 0 || tickets.size() - ticketCount == 1) //있으면 넣는다.
                {
                    ticketCount++;
                    q.push(nextNode);
                    //pq.push(nextNode);
                }
                else
                    visited[i] = false;
            }
            
            //
            if(visited[i] == true) break;
        }
    }
    
    
    return result;
}

 

정답 코드

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

using namespace std;
void DFS(string curr, vector<string> &temp, vector<bool> &visited,
         vector<string> &answer, vector<vector<string>> &tickets, int num);

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;	//순서대로 간 정답
    vector<string> temp;	//다음 갈 곳을 순서대로 넣는다.
    vector<bool> visited(tickets.size());
    
    sort(tickets.begin(), tickets.end());	//알파벳순으로 정렬
    
    DFS("ICN", temp, visited, answer, tickets, 0);
    
    
    return answer;
}

void DFS(string curr, vector<string> &temp, vector<bool> &visited,
         vector<string> &answer, vector<vector<string>> &tickets, int num)
{
    temp.push_back(curr);	//현재 노드를 넣는다.
    
    //방문한 개수와 방문가능한 개수가 동일하고
    //정답의 길이보다 적을때 (선으로 정답이 나온것이 최대길이라면 다음 답이 길이가 같더라도 오답임)
    if(num == visited.size() && answer.size() < num)
    	answer = temp;
    
    for(int i = 0; i < visited.size(); i++)
    {
        if(!visited[i] && tickets[i][0] == curr)	//현재 노드와 출발점이 같을때
        {
            visited[i] = true;	//현재 티켓 사용
            DFS(tickets[i][1], temp, visited, answer, tickets, num + 1);	//다음 장소로 이동
            
            visited[i] = false;	//갔다오고 나서 이것이 최대길이가 아닐 수 있으므로 다른 것을 확인해본다.
        }
    }
    
    temp.pop_back();	//현재 노드를 뺀다.
}

 

풀이

1. 무조건 ICN로 시작한다.
2. 알파벳순으로 빠른 것 먼저 방문한다.
3. 만약 알파벳순으로 갔을 때 모든 티켓을 못 썻을 경우 다음 알파벳이 빠른 순으로 방문
4. 이 때 그 티켓을 기준으로 쭉 들어갔다 나오므로 다른 것을 돌아와서 쉽게 확인 가능