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

-inn·2022년 5월 17일
1

프로그래머스

목록 보기
3/4

여행경로 바로가기

문제 분석

문제 풀이 과정

BFS로 삽질 과정
1. tickets를 알파벳 순으로 정렬
2. 출발지가 ICN인 경우, bfs 돌려서 모든 항공권을 사용한 경우, true 리턴 or false 리턴
3. false인 경우, 다음 ICN 항공권 사용해서 다시 bfs 돌림
4. 테케 1번이 절대 통과되지 않음

❓ 반례
    `입력`
    [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
    `정답`
    ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]

→ WHY ? 가는 도중에 알파벳 순으로 가면 모든 항공권을 쓸 수 없는 길이 끊긴 예외 경우 발생하기 때문 ..

→ 처리할 예외의 경우가 너무 많다 ... 다른 방법 없을까 ?

✅ DFS 재귀 사용하여 모든 경우의 수 체크하면 가능하겠다 !

DFS

  1. tickets를 알파벳 순으로 정렬
  2. dfs(출발지, 사용한 티켓 수) 함수
    • 모든 항공권 다 사용하면 true (알파벳 정렬했기 때문에 무조건 정답)
    • 항공권 다 사용하지 못했는데 길이 끊긴 경우, pop_back()으로 백트랙킹

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> ticket;
vector<string> answer;
bool check[10001];
bool isAnswer;

void dfs(string start, int ticketCnt){
    answer.push_back(start);
    
    if (ticketCnt == ticket.size()) {
        isAnswer = true;
    }
    
    for (int i = 0; i < ticket.size(); i++) {
        if (check[i]) continue;
        if (ticket[i][0] == start) {
            check[i] = true;
            dfs(ticket[i][1], ticketCnt+1);
            
            if (!isAnswer) {
                answer.pop_back();
                check[i] = false;
            }
        }
    }
    
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    ticket = tickets;
    dfs("ICN", 0);
    
    return answer;
}
profile
☁️

0개의 댓글