Notice
Recent Posts
Recent Comments
Link
250x250
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- BOJ
- Algospot
- 유니온파인드
- 완전탐색
- 동적계획법
- 백트래킹
- 알고스팟
- 분할정복
- union-find
- Greedy
- DFS
- 알고리즘문제해결전략
- 백준
- 문자열
- acm
- BFS
- 이분탐색
- priority_queue
- stack
- 분리집합
- 재귀
- 다이나믹프로그래밍
- 너비우선탐색
- 세그먼트트리
- 그리디
- DP
- 종만북
- 누적합
- 스택
- backtracking
Archives
- Today
- Total
DAMPER's 낙서장
오일러 서킷을 찾아내는 알고리즘 본문
728x90
모든 정점이 짝수점(정점의 차수가 짝수인 점)이고, 모든 간선이 하나의 컴포넌트에 포함되어 있다고 가정하자.
함수 findRandomCircuit(u) : 현재 정점에 인접한 간선 중 아직 따라간 적 없는 임의의 간선을 재귀적으로 따라가기를 반복하다가, 더이상 따라갈 간선이 없을 때 종료.
함수를 실행하면 여러 부분 서킷이 생성될텐데, 전체를 포함하는 하나의 서킷을 원하므로 모든 부분 서킷들을 합쳐야한다.
부분 서킷이 생긴다는 말은 무슨 말일까?
어떤 정점에서부터 출발하는 간선이 하나가 아닌 여러개일 수 있는데, 이때 서킷의 정의에 따라 출발하는 간선만큼 해당 정점으로 오는 간선이 존재해야한다. -> 그만큼 부분서킷이 생긴다.
해당 정점에서 나가는 간선이 2개 존재한다면, 2개의 부분 서킷이 생긴다. 이 부분서킷들을 합쳐 하나의 서킷을 만들 수 있다.
findRandomCircuit(u) 함수의 return 과정은 서킷 생성의 역방향으로 이루어진다.
그러므로 return 하면서 vector에 추가해준 후, 함수가 최종적으로 종료하면 vector를 뒤집으면 서킷을 얻을 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
vector<vector<int>> adj;
// adj[i][j] = i와 j 사이의 간선 수
// 무향 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷을 계산한다.
// 결과로 얻어지는 circuit을 뒤집으면 오일러 서킷이 된다.
void getEulerCircuit(int here, vector<int>& circuit)
{
for(int there=0;there<adj.size();++there)
{
while(adj[here][there] > 0)
{
adj[here][there]--;
adj[there][here]--;
getEulerCircuit(there, circuit);
}
}
circuit.push_back(here);
}
|
cs |
각 간선을 따라갈 때마다 getEulerCircuit() 함수를 호출하고, 그 내부에서는 O(|V|)의 반복문을 수행하기 때문에 이 알고리즘의 전체 시간복잡도는 O(|V||E|) 가 된다.
728x90
'Problem Solving > 알고리즘 문제해결전략' 카테고리의 다른 글
무향 그래프에서 단절점 찾기 / 단절선 찾기 (0) | 2022.06.29 |
---|---|
벨만-포드 최단경로 알고리즘 (0) | 2021.04.17 |
[ALGOSPOT] 단어 제한 끝말잇기 (WORDCHAIN) (0) | 2021.02.18 |
오일러 서킷 (Eulerian circuit) (0) | 2021.02.16 |
[ALGOSPOT] 고대어 사전 (DICTIONARY) (0) | 2021.02.09 |