백준19614 Travelling Salesperson

작성일 | In

문제 링크

  • http://icpc.me/19614

문제 출처

  • 2020 CCO Day2 1번

사용 알고리즘

  • 연결 리스트

시간복잡도

  • $O(N^2)$

풀이

정점을 하나씩 추가해서 경로를 만드는 방식으로 진행합니다.

지금까지 만든 경로를 $(v_1, v_2, \cdots, v_k)$, RR...RBB...B 형태라고 합시다.
새로운 정점 $x$를 추가할 때 만약 $(x, v_1)$ 간선이 R이면 앞에 추가하고 $(v_k, x)$ 간선이 B이면 뒤에 추가하면 됩니다. 두 가지 경우에 모두 해당하지 않는다면 $(x, v_1)$이 B, $(v_k, x)$가 R인 상태입니다.
만약 $(v_1,v_k)$가 R이면 $v_k$를 $v_1$ 앞에 붙인 다음, $(x,v_k)$가 R이니까 $x$를 앞에 붙이면 됩니다. 그렇지 않다면 $(v1,v_k)$가 B일 텐데, 이때는 $v_k$ 뒤에 $v_1$을 붙인 다음 $x$를 뒤에 붙이면 됩니다.

남은 부분은 원하는 정점을 시작 정점으로 만드는 것입니다. 시작 정점을 가장 마지막에 추가한 다음, 만약 시작 정점이 맨 뒤로 갔다면 경로를 뒤집어서 시작 정점이 되도록 보장할 수 있습니다.

연결 리스트를 사용하면 시작점마다 $O(N)$ 시간이 걸려서 총 $O(N^2)$ 시간에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int N, A[2020][2020];

void Solve(int src){
    list<int> res;
    function<void(int)> add = [&res](int v){
        if(res.size() <= 1){ res.push_back(v); return; }
        int a = *res.begin(), b = *res.rbegin();
        if(A[v][a] == 0) res.push_front(v);
        else if(A[v][b] == 1) res.push_back(v);
        else if(A[a][b] == 0) res.pop_back(), res.push_front(b), res.push_front(v);
        else res.pop_front(), res.push_back(a), res.push_back(v);
    };

    for(int i=1; i<=N; i++) if(i != src) add(i);
    add(src);
    if(*res.begin() != src) res.reverse();

    cout << N << "\n";
    for(auto i : res) cout << i << " ";
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=2; i<=N; i++) for(int j=1; j<i; j++) { char c; cin >> c; A[i][j] = A[j][i] = c == 'B'; }
    for(int i=1; i<=N; i++) Solve(i);
}