[프로그래머스] 여행경로

문제

여행경로 (https://programmers.co.kr/learn/courses/30/lessons/43164)

풀이

1. 초기 접근

• 문제 조건 해석
  • 연속된 경로 출력 -> DFS 문제다.
  • 주어지는 공항 수 n이 3 이상 10000 미만 -> O(n^2) 으로 해결가능하다.
  • 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로가 정답 -> 정렬 작업이 필요하다.
• 코드

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

using namespace std;

void dfs(string from, vector<vector<string>>& tickets, vector<bool>& visit, vector<string>& answer) {

    answer.push_back(from);
    for (int i=0 ; i<tickets.size() ; i++) {
        if (tickets[i][0] == from && visit[i] == false) {
            visit[i] = true;
            dfs(tickets[i][1], tickets, visit, answer);
            return;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> visit(tickets.size(), false);

    sort(tickets.begin(), tickets.end());
    dfs("ICN", tickets, visit, answer);

    return answer;
}

2. 오류

• 문제 조건 해석 오류

  • 모든 도시를 방문할수 없는 경우는 주어지지 않는다.

    이 조건을 생각하고, 위에 같이 하면 될 것이라고 그냥 naive 하게 생각했던 듯 하다. 위 코드대로 작성할 시, test case 4개중 2개만 충족해서 틀렸다고 한다. 처음에 갈피를 못잡아, 헤마다가 BOJ Slack 에서 답을 얻을 수 있었다.

    그래프를 생각해보자. 예를 들어, 아래와 같은 경로가 주어졌다고 하자.

    • 1->2
    • 1->3
    • 3->1

    위 알고리즘 대로라면, 1->2 만 하고 끝나버릴 것이다. 왜냐하면 2-> 로 시작하는 경로가 없기 때문이다. 그런데 사실 정답은 1->3->1->2 가 된다.

    즉 위 코드에서 놓친 것이 있다. dfs 로 해당 경로를 계속해서 탐색할 때, 그 경로로 모든 도시를 방문할 수 있는지 없는지에 대한 여부이다. 위 조건을 다시 잘 보면, 방문할 수 없는 경우가 주어지지 않는다는 것이지, 그렇다고 모든 경로가 다 이어진다는 것은 아니다. 이어지는 경로인지 아닌지는 결국 체크해야 한다.

3. 정답

• 수정한 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool dfs(string from, vector<vector<string>>& tickets, vector<bool>& visit, vector<string>& temp, vector<string>& answer, int cnt) {

    temp.push_back(from);

    if (cnt == tickets.size()) {
        answer = temp;
        return true;
    }

    for (int i=0 ; i<tickets.size() ; i++) {
        if (tickets[i][0] == from && visit[i] == false) {
            visit[i] = true;

            bool success = dfs(tickets[i][1], tickets, visit, temp, answer, cnt+1);
            if (success)
                return true;
            visit[i] = false;
        }
    }
    temp.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer, temp;
    vector<bool> visit(tickets.size(), false);

    sort(tickets.begin(), tickets.end());
    dfs("ICN", tickets, visit, temp, answer, 0);

    return answer;
}

• 경로 끝까지 다 이어졌는지 확인.

if (cnt == tickets.size()) {
        answer = temp; // save current path.
        return true;
}

• 경로 찾기에 성공한 경우, 더 이상 dfs를 진행하지 않아야 하므로

bool success = dfs(tickets[i][1], tickets, visit, temp, answer, cnt+1);
if (success)
    return true; // exit dfs.