<div id="readability-page-1" class="page"><div>
 

 <header id="header" itemscope="" itemtype="http://schema.org/WPHeader">
 
 </header>

 <main id="main">
 <div id="content">
 
 

 

 
 
 

 <article itemscope="" itemtype="http://schema.org/Article">
 

 

 

 
 <header>

 
 
 
 

 
 </header>
 

 <div itemprop="articleBody">
 
 
 
 

 
 
 
 












 <h3 id="문제-링크">문제 링크</h3>
<ul>
 <li>http://icpc.me/19614</li>
</ul>

<h3 id="문제-출처">문제 출처</h3>
<ul>
 <li>2020 CCO Day2 1번</li>
</ul>

<h3 id="사용-알고리즘">사용 알고리즘</h3>
<ul>
 <li>연결 리스트</li>
</ul>

<h3 id="시간복잡도">시간복잡도</h3>
<ul>
 <li>$O(N^2)$</li>
</ul>

<h3 id="풀이">풀이</h3>
정점을 하나씩 추가해서 경로를 만드는 방식으로 진행합니다.

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

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

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

<h3 id="전체-코드">전체 코드</h3>
<div><table><tbody><tr><td><pre>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</pre></td><td><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;

int N, A[2020][2020];

void Solve(int src){
 list&lt;int&gt; res;
 function&lt;void(int)&gt; add = [&amp;res](int v){
 if(res.size() &lt;= 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&lt;=N; i++) if(i != src) add(i);
 add(src);
 if(*res.begin() != src) res.reverse();

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

int main(){
 ios_base::sync_with_stdio(false); cin.tie(nullptr);
 cin &gt;&gt; N;
 for(int i=2; i&lt;=N; i++) for(int j=1; j&lt;i; j++) { char c; cin &gt;&gt; c; A[i][j] = A[j][i] = c == 'B'; }
 for(int i=1; i&lt;=N; i++) Solve(i);
}
</code></pre></td></tr></tbody></table></div>


 
 </div>

 

 

 

 
 </article>

 
</div>
 </main>

 

 
 
 

 </div></div>

JusticeHui가 PS하는 블로그

문제 링크
http://icpc.me/19614
문제 출처
2020 CCO Day2 1번
사용 알고리즘
연결 리스트
시간복잡도
$O(N^2)$
풀이
정점을 하나씩 추가해서 경로를 만드는 방식으로 진행합니다.
지금까지 만든 경로를 $(v_1, v_2, \cdots, v_k)$, RR...RBB...B 형태라고 합시다.
R이면 앞에 추가하고 $(v_k, x)$ 간선이 B이면 뒤에 추가하면 됩니다. 두 가지 경우에 모두 해당하지 않는다면 $(x, v_1)$이 B, $(v_k, x)$가 R인 상태입니다.
R이면 $v_k$를 $v_1$ 앞에 붙인 다음, $(x,v_k)$가 R이니까 $x$를 앞에 붙이면 됩니다. 그렇지 않다면 $(v1,v_k)$가 B일 텐데, 이때는 $v_k$ 뒤에 $v_1$을 붙인 다음 $x$를 뒤에 붙이면 됩니다.
남은 부분은 원하는 정점을 시작 정점으로 만드는 것입니다. 시작 정점을 가장 마지막에 추가한 다음, 만약 시작 정점이 맨 뒤로 갔다면 경로를 뒤집어서 시작 정점이 되도록 보장할 수 있습니다.
연결 리스트를 사용하면 시작점마다 $O(N)$ 시간이 걸려서 총 $O(N^2)$ 시간에 문제를 해결할 수 있습니다.
전체 코드
#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 <> 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);
}

백준19614 Travelling Salesperson

댓글