깊이 우선탐색
#1 도입
DFS의 중요한 특성은 더 따라갈 간선이 없다면 이전으로 되돌아 간다는 점인데, 재귀 호출을 이용하면 함수가 종료하면 호출한 위치로 다시 돌아가기 때문에 간단히 구현 할 수 있다.
시간 복잡도 : $O(V+E)$
#2 위상 정렬
이수 체계도와 같이 작업 간에 순서가 존재할 때, 의존 관계를 DAG의 간선으로 표현할 수 있다.
이때 의존성 그래프의 정점을 배열하는 문제를 위상정렬 이라고 한다.
<Indegree체크하는 방식>
- indegree 가 0인 정점을 큐에 넣는다.
- 큐에서 정점을 꺼내고 위상 정렬 결과에 추가한다
- 그 정점에 연결된 정점의 indegree 1감소, 0이면 큐에추가
<DFS방식>
- dfsAll() 을 수행하며 dfs가 종료할때마다 현재 정점의 번호를 기록하고 dfsAll() 종료시 순서를 뒤집는다.
[백준3665 최종 순위]https://www.acmicpc.net/problem/3665
- 두팀의 순위 바뀌는 것을 그 두팀사이의 간선 방향만 바꿔주는 것으로 처리할 수 있는 이유는
올바른 입력의 경우 상대적인 순위가 바뀐 모든 팀의 목록을 주기 때문이다. - 큐의 사이즈가 2이상이 되면 ? , 사이클이 생기면 IMPOSSIBLE 이다
- 사이클이 생기면 큐에 안들어가는 팀이 생긴다.
[알고스팟 DICTIONARY]https://www.algospot.com/judge/problem/read/DICTIONARY
- 순서에 모순이 있다 == 사이클이 존재한다.
#3오일러 서킷
그래프의 모든 간선을 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제
오일러 서킷은 모든 정점에 들어가는 횟수와 나오는 횟수가 같아야 하므로, 한 정점에 인접한 간선의 수 즉 정점의 차수(degree) 가 짝수이어야 한다.
모든 정점이 차수가 짝수인 짝수점이고, 하나의 컴포넌트를 이룬다면 오일러 서킷은 항상 존재할까?
오일러 서킷을 찾아내는 알고리즘
- 정점$u$ 에서 시작해 아직 지나지 않은 간선중 하나를 따라가며 임의의 경로를 만드는 함수$findRandomCircuit(u)$ 를 만들어보자. 이 함수는 더이상 따라갈 간선이 없을 때 종료한다.
- 모든 점이 짝수점이기에 경로는 항상 시작점에서 끝나게 된다
- 서킷이 모든 간선을 지나쳤다면 오일러 서킷을 찾은 것이고, 아니라면 서킷의 정점을 조사해보면 따라가지 않은 간선이 남아있는 정점$v$이 존재 할 수 밖에 없다.
- $v$ 또한 짝수점이었기에, $v$에 남아있는 간선도 짝수개이다. 따라서 $v$ 에서 다시 함수를 수행하면 새로운 서킷을 얻게된다.
- 처음에 찾은 서킷을 $v$ 에서 자른 후 새로운 서킷을 끼워넣으면 하나의 큰 서킷을 만들 수 있다.
- 이와 같은 작업을 모든 간선을 포함할 때 까지 반복하면 오일러 서킷을 찾을 수 있다.
DFS를 이용한 오일러 서킷의 구현
vector<vector<int>> adj;
void getEulerCircuit(int here,vector<int>& circuit) {
for(int there = 0; there<adj[here].size();there++) {
while(adj[here][there]>0) {
adj[here][there]--;
adj[there][here]--;
getEulerCircuit(there,circuit);
}
}
circuit.push_back(here);
}
정점에 아직 간선이 남아있는 지 확인하고, 새 서킷을 만들어 원래 서킷에 붙이는 코드를 따로 작성하지 않았는데, 이는 재귀호출이 끝날 때 간선을 서킷에 추가하는 방법으로 해결이 가능하다.
따라서 $circuit$에는 경로의 역순으로 간선이 추가되므로 지금까지 DFS로 탐색한 서킷의 뒷부분만이 저장되어 있다. 따라서 어떤 정점에서 새 서킷을 찾더라도 그냥 지금 만든 부분에 이어붙이면 저절로 끼워 넣은 효과를 낸다.
방향그래프의 경우 얻은 서킷을 뒤집어서 우리가 찾는 오일러 서킷을 얻는다.
- 오일러 트레일 : 모든 간선을 한 번씩만 지나지만, 시작점과 끝점이 다른 경로 간단하게 끝점에서 시작점으로 향하는 간선을 추가한뒤 오일러 서킷을 찾고 그 간선을 지워주면 오일러 트레일을 찾을 수 있다. 시작점과 끝점은 홀수점이고 두점을 제외한 모든 점이 짝수점이면 오일러 트레일이 존재한다
[알고스팟 WORDCHAIN]https://www.algospot.com/judge/problem/read/WORDCHAIN
직관적으로 처음 떠오르는 그래프는 각 단어를 정점으로 하는 방향그래프이다. need → dog 와 같은 간선을 떠올릴 수 있다.
그러나 모든 단어를 사용하고 게임을 완료하는 것이 이 문제의 목표이고, 정점에 단어가 들어있다면, 모든 정점을 한 번씩 거치는 경로가 있는지를 판단해야 한다. 이는 해밀턴 경로이며 해밀턴 경로를 찾는 유일한 방법은 조합탐색으로 모든 정점의 배열을 하나하나 시도해야 하기 때문에 $O(n!)$
간선에 단어를 넣을 방법을 고안해보면, 각 단어의 시작알파벳에서 마지막 알파벳으로 가는 간선에 단어를 넣을 수 있다. 그러면 모든 간선을 한번 씩만 지나는 경로가 존재하는가에 대한 문제로 바뀐다.
vector<vector<int>> adj;
vector<string> graph[26][26];
vector<int> indegree;
vector<int> outdegree;
void makeGraph(const vector<string>& words) {
for(int i=0;i<26;i++) {
for(int j=0;j<26;j++) {
graph[i][j].clear();
}
}
adj = vector<vector<int>>(26,vector<int>(26));
indegree = vector<int>(26);
outdegree = vector<int>(26);
for(int i=0;i<words.size();i++) {
int st = words[i][0]-'a';
int en = words[i][words[i].size()-1]-'a';
adj[st][en]++;
indegree[en]++;
outdegree[st]++;
graph[st][en].push_back(words[i]);
}
}
방향그래프이기 때문에, indegree , outdegree를 나누어 세어야 하며, 어떤 단어를 사용했는지 알아야 하기에 graph에 단어를 저장해준다.
bool checkEuler() {
int plus1 = 0; int minus1 = 0;
for(int i=0;i<26;i++) {
int delta = outdegree[i]-indegree[i];
if(delta<-1||delta>1) return false;
if(delta==1) plus1++;
if(delta==-1) minus1++;
}
return (plus1==1 && minus1==1)|| (plus1==0 && minus1==0);
}
오일러 경로or 오일러 트레일이 될 수 있는가를 먼저 판정해주어야 한다. 오일러 경로는 모든 정점이 짝수점, 오일러 트레일은 끝점과 종료점만 홀수점인 것을 떠올려야 한다.
void getEulerCircuit(int here,vector<int>& circuit) {
for(int there = 0; there<adj[here].size();there++) {
while(adj[here][there]>0) {
adj[here][there]--;
getEulerCircuit(there,circuit);
}
}
circuit.push_back(here);
}
vector<int> getEulerTrailOrCircuit() {
vector<int> circuit;
for(int i=0;i<26;i++) {
if(outdegree[i] == indegree[i]+1) {
getEulerCircuit(i,circuit);
return circuit;
}
}
for(int i=0;i<26;i++) {
if(outdegree[i]!=0) {
getEulerCircuit(i,circuit);
return circuit;
}
}
return circuit;
}
오일러 트레일이라면 오일러 트레일을, 오일러 경로라면 오일러 경로를 위에서 학습한 내용대로 구현
마지막으로 1개의 컴포넌트가 아닐 경우를 대비해, 위 함수로 구한 circuit의 크기가 words.size()+1 인지 확인하면 정답을 구할 수 있다.
정리해보면
- 오일러 회로는 1개의 컴포넌트이며, 모든 정점이 짝수점이다.
- DFS를 돌리면서 중간에 방문하지 않은 간선이 남아있는 정점에서는 새로운 경로를 현재경로에 붙인다.
- 방향그래프라면 $circuit$을 뒤집는다.
[백준 1591 수열복원]https://www.acmicpc.net/problem/1591
- $1:2:3:2:1:2:3:4:2$ 수열을 보자. 현재 상황은 모든 부분 수열을 순서대로 배치하면 답을 얻을 수 있지만, 어떤 것이 한 부분수열 뒤에 와야할지를 정하지 못하는 상황이다. 하지만 123뒤에 342는 절대아니고 232 or 234가 와야함 정도만 알고있다.
- 즉 하나빼고 겹치는 부분수열이 뒤에와야 하는데 어느것이 와야하는지 알 수가 없다. 어느것이 와야하는지 몰라도 답을 구하는 법은 없을까? 남은 조건은 부분수열을 전부 사용해야 한다는 것
- DFS를 이용하면 어떤것을 먼저 붙이던지 DFS종료시에 값을 추가하고 뒤집는다면 상관없겠다 아하 오일러 경로문제구나!
- 부분수열의 $[0:m-2]$ 을 앞쪽정점$a$, $[1:m-1]$ 을 뒷쪽정점$b$ 라고 한다음, 간선 $a→b$ 를 추가하면 3에서 구한 풀이를 쉽게 구현할 수 있다.
[백준 18250 철도 여행]https://www.acmicpc.net/problem/18250
“모든 노선을 단 한번, 도시는 상관없이” 에서 오일러 경로를 떠올려 보자. 하나의 컴포넌트를 도는데 몇번의 여행이 필요할까??
양방향 그래프에서 한 정점이 홀수개의 간선을 가진다면, 출발점이 되거나 도착점이 되는데, 오일러 경로, 즉 한붓그리기로 갈 수 있는 최대 범위가 하나의 홀수점에서 다른 홀수점까지이다.
따라서 홀수점이 존재한다면 필요한 여행의 횟수는 홀수점/2, 짝수점만 존재한다면 오일러 경로이므로 1번
간선 1개당 2개의 정점의 값에 영향을 미치므로 홀수점은 짝수개이다.
#4 DFS 간선 분류
DFS를 수행하면 모든 간선을 한 번씩 만나게 되며, 처음 따라가는 간선을 모아보면 트리 형태를 띠게 된다. 이 트리를 DFS Spanning Tree라고 부른다. 트리를 이용해 그래프의 모든 간선을 분류해보자
- Tree Edge : Spanning Tree에 포함되는 간선
- Forward Edge : Spanning Tree의 선조에서 자식으로 향하지만 Tree Edge가 아닌 간선
- Backward Edge : Spanning Tree의 자식에서 선조로 향하는 간선
- Cross Edge : 선조와 자식관계가 아닌 정점들 간에 연결된 간선
댓글남기기