프로그래머스 43164 - 여행경로 (c++)

프로그래머스 43164 - 여행경로

문제 링크

접근 및 생각

• 문제는 DFS 방식으로 풀이하였다. 왜냐하면 알파벳 순서에 대한 처리가 필요했기 때문이다.
  • DFS에 대한 설명은 (링크)를 참조.
  • DFS란 깊이 우선 탐색으로써 일단 깊게 들어가서 leaf node에 닿아, 탐색한 경로가 답에 걸맞기만 하면 그걸 쓰면 된다.
  • 이 점을 사용해서, 미리 tickets를 알파벳 순서로 배열을 한 뒤에 DFS하기로 했다_ .
  • 미리 tickets를 알파벳 순서로 배열을 한 뒤에 DFS를 하면, 제일 빨리 찾은 답이 알파벳 순서가 맞는 답일 것이다.
  • tickets를 나열하는 cmp 함수

      // 티켓의 시작 주소 오름차순이 1순위, 티켓의 도착 주소 오름차순이 2순위
      bool cmp(vector<string> a, vector<string> b){
          if(a[0] == b[0]){
              return a[1] < b[1];
          }
          return a[0] < b[0];
      }

• DFS의 포인트는
  • DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가 ,
  • DFS의 초깃값을 어떻게 잡을 것인가 ,
  • 언제 DFS를 멈추게 할 것인가 ,
  • DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가

DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가

• 여러 경우의 수가 있겠지만, 필자는 이제까지 이동한 경로를 넣었다.

    void dfs(vector<string> path);

DFS의 초깃값을 어떻게 잡을 것인가

• 시작 도시는 ICN이다.

    dfs({"ICN"});

언제 DFS를 멈추게 할 것인가

• 반환되는 벡터의 크기는 늘 tickets 벡터 크기 + 1이므로, path 벡터 크기가 tickets 벡터 크기 + 1 이라면 DFS를 멈춘다.

    if(path.size() == t.size() + 1){
        if(answer.empty()){
            answer = path;
        }
    }

• 또한, 가장 먼저 찾은 경로를 answer로 쓸 것이기 때문에 다음과 같은 코드를 추가하였다.

    if(!answer.empty()) return;

DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가

• 아직 사용하지 않은 티켓이고, path의 마지막 원소가 티켓의 시작 주소라면, 그 티켓을 탐색할 수 있다.

    for(int i = 0; i < t.size(); i++){
        if(used[i] == 0 && temp == t[i][0]){
            used[i] = 1;
            path.push_back(t[i][1]);
            dfs(path);
            used[i] = 0;
            path.pop_back();
        }
    }

코드

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

vector<vector<string>> t;
vector<int> used;
vector<string> answer;

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

void dfs(vector<string> path){
    if(!answer.empty()) return;

    string temp = path[path.size() - 1];
    if(path.size() == t.size() + 1){
        if(answer.empty()){
            answer = path;
        }
    }
    else{
        for(int i = 0; i < t.size(); i++){
            if(used[i] == 0 && temp == t[i][0]){
                used[i] = 1;
                path.push_back(t[i][1]);
                dfs(path);
                used[i] = 0;
                path.pop_back();
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    t = tickets;
    used.assign(t.size(), 0);
    sort(t.begin(), t.end(), cmp);
    dfs({"ICN"});
    return answer;
}

채점 결과