오일러 회로, 경로 문제

* 오일러 회로

* 백준 온라인 저지

1. 오일러 회로 (https://www.acmicpc.net/problem/1199)

  문제 이름부터가 오일러 회로다.. ㅎㅎ 가장 기본적인 오일러 회로를 따라가면 된다.

  또한 무방향 그래프이기 때문에 방향성에 대해 확인할 필요가 없다.

  기초적인 오일러 회로가 있는지 확인한 뒤, DFS를 돌리면 된다.

인접 행렬 코드 :

#include <cstdio>
#include <vector>
using namespace std;
int adj[1000][1000], n;
vector<int> c;
void eulerianCircuit(int u) {
	for(int v=0;v<n;v++)
		while (adj[u][v]) {
			adj[u][v]--;
			adj[v][u]--;
			eulerianCircuit(v);
		}
	c.push_back(u);
}
int main() {
	int i, j, deg[1000] = {},f=1;
	scanf("%d", &n);
	for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
		scanf("%d", &adj[i][j]);
		deg[i] += adj[i][j];
	}
	for (i = 0; i < n; i++)
		f &= (deg[i] && !(deg[i]%2));
	if (f) {
		eulerianCircuit(0);
		for (i = 0; i < c.size(); i++)
			printf("%d ", c[c.size()-i-1] + 1);
	}
	else printf("-1");
	return 0;
}

인접 리스트 코드 :

#include <cstdio>
#include <vector>
using namespace std;
int n;
struct _e {
	int t, c, rn;
	void setData(int to, int cap, int rev_n) {
		t = to, c = cap;
		rn = rev_n;
	}
	void del(int amt, vector<_e> adj[]) {
		c -= amt;
		adj[t][rn].c -= amt;
	}
};
vector<_e> adj[1000];
void addEdge(int u, int v, int cap) {
	_e uv, vu;
	uv.setData(v, cap, adj[v].size());
	vu.setData(u, cap, adj[u].size());
	adj[u].push_back(uv);
	adj[v].push_back(vu);
}

vector<int> c;
void eulerianCircuit(int u) {
	for (_e& e : adj[u]) {
		while (e.c) {
			e.del(1, adj); // 간선 하나를 지운다.
			eulerianCircuit(e.t);
		}
	}
	c.push_back(u);
}
int main() {
	int i, j, deg[1000] = {}, f = 1,cap;
	scanf("%d", &n);
	for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
		scanf("%d", &cap);
		deg[i] += cap;
		if (i >= j) continue;
		addEdge(i, j, cap);
	}
	for (i = 0; i < n; i++)
		f &= (deg[i] && !(deg[i] % 2));
	if (f) {
		eulerianCircuit(0);
		for (i = 0; i < c.size(); i++)
			printf("%d ", c[c.size() - i - 1] + 1);
	}
	else printf("-1");
	return 0;
}

* 오일러 경로

  오일러 경로 문제의 특징은 여러 데이터 간의 관계도를 세우고 이를 일정한 순서로 나열하는 데에 있다. 관계도는 문제에서 주어지지 않고 각 데이터 간의 관계를 직접 정립하여 데이터를 간선으로 보고, 모든 데이터를 사용하는 걸로 볼 수 있다. 또한 방향 그래프의 경우 조금 복잡해지는데, 이는 시작점과 도착점을 찾고, 오일러 회로를 돌려야 하기 때문이다.

  오일러 경로의 대표적인 예로는 DNA 염기 순서를 재배열하는 것이다. 실제로 구글링으로 찾아봐도 DNA 예제가 엄청 많다.

* Algospot

1. 단어 제한 끝말잇기 (https://algospot.com/judge/problem/read/WORDCHAIN)

  단어 하나를 간선으로 생각해보자. 그러면 정점은 단어의 첫 글자와 마지막 글자들의 집합으로 이뤄질 수 있다. 끝말 잇기가 되려면 모든 단어를 사용해야하고, 이는 곧 모든 간선을 사용해야 한다.

  그 다음, 만들 그래프가 방향인지 무방향인지 판단해보자. apple라는 단어를 보면, a로 시작하여 e로 끝난다. 이를 e로 시작하여 a로 끝나는 간선으로 볼 수 없기 때문에 방향 그래프로 설정해야 한다.

  방향 그래프임을 알았으니, 이는 오일러 회로일까? 오일러 경로일까? 답은 주어지는 데이터에 따라 달라진다.

  만약 abc cdf fea 라는 단어가 들어왔다면 어디로든 시작해도 상관이 없기 때문에(사이클을 이루기 때문) 오일러 회로가 된다. 하지만 abc cdf feg 라는 단어가 들어왔다면 a로 시작해서 g로 끝나는 오일러 경로를 찾아야 한다. 따라서 해당 그래프가 오일러 회로로 이뤄지는지 아니면 오일러 경로인지 먼저 판단해야 한다. 판단 근거는 진입 차수와 진출 차수를 계산하면 된다.

  또한 모든 간선을 거쳤다면 vector에 저장된 데이터의 수는 간선의 수+1와 같다.

코드 :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N, adj[26][26];
vector<char*> edge[26][26];
vector<int> c;
void dfs(int u) {
	for (int v = 0; v<26; v++)
		while (adj[u][v] > 0) {
			adj[u][v]--;
			dfs(v);
		}
	c.push_back(u);
}
int main() {
	char words[100][11];
	int C, i, j, L[100], ind[100], outd[100], u, v, f, p, m, invalid;
	scanf("%d", &C);
	while (C--) {
		p = m = invalid = 0;
		scanf("%d\n", &N);
		c.clear();
		memset(adj, 0, sizeof adj);
		for (i = 0; i < 26; i++) {
			for (j = 0; j < 26; j++)
				edge[i][j].clear();
			ind[i] = outd[i] = 0;
		}
		for (i = 0; i < N; i++) {
			scanf("%s", words[i]);
			L[i] = strlen(words[i]);
			u = words[i][0] - 'a', v = words[i][L[i] - 1] - 'a';
			edge[u][v].push_back(words[i]);
			adj[u][v]++;
			ind[v]++;
			outd[u]++;
		}
		
		for (i = 0; i < 26; i++) {
			int delta = outd[i] - ind[i];
			if (delta < -1 || 1 < delta) invalid = 1;
			if (delta == 1) p++;
			if (delta == -1) m++;
		}
		invalid |= !((p == 1 && m == 1) || (p == 0 && m == 0));
		if (!invalid) {
			f = 1;
			for (i = 0; i < 26 && f; i++) {
				if (outd[i] == ind[i] + 1) {
					dfs(i);
					f = 0;
				}
			}
			for (i = 0; i < 26 && f; i++) {
				if (outd[i]) {
					dfs(i);
					f = 0;
				}
			}
		}		
		if (invalid || c.size() != N + 1) printf("IMPOSSIBLE");
		else {
			reverse(c.begin(), c.end());
			for (i = 0; i < c.size() - 1; i++) {
				printf("%s ", edge[c[i]][c[i + 1]].back());
				edge[c[i]][c[i + 1]].pop_back();
			}
		}
		puts("");
	}
	return 0;
}

* Codeforces

1. Tanya and Password (http://codeforces.com/contest/508/problem/D)

  길이가 3뿐이라서 연관성에 대해 생각해보자. 이번엔 단어 자체를 간선에 넣을 수는 없다. 겹치는 부분이 두 군데이기 때문에 단어 시작과 끝을 정점으로 보면 반드시 중복되는 부분이 발생해 n+2보다 긴 길이의 답을 도출할 수 있다.

  Greedy하게 접근한다면 굳이 간선에 무언갈 넣지 않아도 된다는 것을 알 수 있다. 다시 말하자면 A 다음으로 B가 올 수 있다면 A + (B의 끝글자)로 이룰 수 있다. 그렇다면 정점을 어떻게 설정해야 할까?

  정점의 경우 단어간 겹치는 부분을 생각해보자. 반드시 2글자가 겹치게 되어 있다. 만약 오일러 경로라면 두 단어를 제외한 나머지는 필수적으로 두 번씩 겹치게 되어 있다.

ABC

BCD

CDE

DEZ

-> ABC -> BCD -> CDE -> DEZ

-> answer : ABCDEZ

  ABC, DEZ만 각각 뒤 앞으로 겹치고, 나머지는 앞뒤로 한 번씩 겹치게 되어 있다.

  따라서 겹치는 부분(2글자씩)을 정점으로 본다면 오일러 경로 및 오일러 회로를 찾을 수 있다.

  단어 s에 대해 정점 s[0]s[1]에서 정점 s[1]s[2]로 간선을 추가해주자. 위의 예시에서는 오일러 경로이기 때문에 AB부터 시작해서 EZ로 끝나는 오일러 경로를 찾을 수 있다. (그림을 그린다면 직관적이다)

코드 :

#include <cstdio>
#include <vector>
#include <map>
using namespace std;

const int MAX_V = 4000;
map<pair<char, char>, int> mss;
int iv[MAX_V];
vector<int> c;
vector<int> adj[MAX_V];
int v_cnt = 0;
int toV(char a, char b) {
	auto p = make_pair(a, b);
	if (mss.find(p) == mss.end()) {
		mss.insert(make_pair(p, v_cnt));
		iv[v_cnt] = (int)a * 1000 + b;
		v_cnt++;
	}
	return mss[p];
}

void dfs(int u) {
	while (adj[u].size()) {
		int v = adj[u].back();
		adj[u].pop_back();
		dfs(v);
	}
	c.push_back(u);
}

int main() {
	char s[4];
	int n, i, u, v, ind[MAX_V] = {}, outd[MAX_V] = {},p=0,m=0,invalid=0,del,f;
	scanf("%d\n", &n);
	for (i = 0; i < n; i++) {
		scanf("%s", s);
		u = toV(s[0], s[1]), v = toV(s[1], s[2]);
		adj[u].push_back(v);
		ind[v]++;
		outd[u]++;
	}
	for (i = 0; i < v_cnt; i++) {
		del = ind[i] - outd[i];
		if (del < -1 || del > 1) invalid = 1;
		if (del == 1) p++;
		if (del == -1) m++;
	}
	invalid |= !(p == 1 && m == 1 || !p && !m);
	if (invalid) printf("NO");
	else {
		f = 1;
		for (i = 0; i < v_cnt && f; i++)
			if (outd[i] == ind[i] + 1) {
				dfs(i);
				f = 0;
			}
		for (i = 0; i < v_cnt && f; i++)
			if (outd[i]) {
				dfs(i);
				f = 0;
			}
		if (c.size() != n + 1) printf("NO");
		else {
			puts("YES");
			printf("%c", (char)(iv[c[c.size() - 1]] / 1000));
			for (i = c.size() - 1; i >= 0; i--)
				printf("%c", (char)(iv[c[i]] % 1000));
		}
	}

	return 0;
}

  2. One-way Reform (http://codeforces.com/contest/723/problem/E)

  갑자기 난이도 급상승..은 기분탓이 아니다. 

  진짜 신박할 정도로 재밌고 창의적인 문제를 인정하지 않을 수 없다. 혹시나해서 해당 커뮤니티 사람들의 리뷰를 읽어보면 이 문제의 editorial이 매우 아름답다(elegant)고 칭찬 일색이다.

  문제를 쉽게 말하자면 여러 component에서 각 도시에 연결된 양방향 간선을 단방향 간선으로 변경하여 한 방향으로만 바꿀 때, 진입 도로(진입 차수)와 진출 도로(진출 차수)가 같은 도시의 수를 최대로 하겠다는 것이다.

  우선 도시에 연결된 도로를 삭제할 수는 없으므로, 도로의 수가 홀수라면 절대로 진입 차수와 진출 차수가 같을 수 없다. 따라서 문제에서 원하는 도시의 자격 조건1은 연결된 차수의 수가 짝수여야 한다는 점이다.

[도시 조건] 하나의 도시에 연결된 차수가 반드시 짝수여야 한다.

  또한 문제 조건은 진입 차수와 진출 차수가 같은 도시의 수를 최대화 시키고 싶은 것이기 때문에 오일러 회로의 특성을 이용하도록 한다. 이는 오일러 회로 및 경로의 속성을 이용한 것인데, 양방향 그래프에서 진입 차수와 진출 차수를 같게하는 경로가 존재한다면 그것은 곧 모든 도시에 대해 진입 차수와 진출 차수가 같다는 의미와 동치이기 때문이다(오일러 경로의 경우 시작점과 도착점 제외).

  짝수 차수를 갖는 도시를 '짝도시'(내맘대로 줄이기~)라고 줄이고, 여러 짝도시 중에 문제에 만족하는 도시가 될 수 없는 짝도시를 생각해보자.

  Component 단위로 생각해보면,

1. 도로로 연결된 도시가 모두 짝도시

  모든 도시가 짝도시라면 Eulerian cycle을 이루는 조건을 만족하기 때문에, 한 방향으로 흐르는 사이클을 필연적으로 찾을 수 있다.

2. 정확히 두 개가 홀수 차수를 갖는 Component

  마찬가지로 Eulerian path를 이루는 조건을 만족하기 때문에, 한 방향으로 흐르는 사이클을 마지막 간선을 제외한 경로를 찾을 수 있다.

3. 세 개 이상의 홀수 차수를 갖는 Component

  각각 홀수 도시가 차수가 하나 많은 것을 생각해보자. 일방통행으로 도로를 재구성하기 때문에, 홀수 도시의 마지막 하나 차수는 진입 차수 아니면 진출 차수 중 둘 중 하나다.

  잠시 다른 얘기로 돌아와서, 이 Component 내의 짝도시에 대해 문제에서 원하는 도시가 되기 위해서는 방향성을 어떻게 정해야 하는지 알아보자. [도시 조건]에 의해 홀도시는 절대로 만족하는 도시가 될 수 없다. 그렇다면 홀도시와 짝도시가 연결된 도로의 방향성을 생각해보면 홀도시가 짝도시에게 맞춰주는 쪽으로 도로 방향을 설정할 수 있다. 그렇다면 짝도시 끼리는 어떨까? 짝도시끼리는 반드시 사이클을 가지고 있기 때문에 오일러 회로로 진입 및 진출 차수를 모두 같게 할 수 있다. 따라서 정리하자면 아래를 도출할 수 있다.

[Greedy 접근] 하나의 도시에 연결된 차수가 짝수라면 진입 차수와 진출 차수를 같게하는 경우는 반드시 존재한다.

=> 도시에 연결된 도로의 수가 짝수라면 문제에서 만족하는 도시가 된다.

  여기서 홀수 차수를 갖는 도시의 마지막 도로로 연결된 짝도시를 생각해보면, 그 마지막 도로의 방향에 따라 짝도시가 문제에서 만족하는 도시인지 아닌지 판단의 근거가 된다.

  다시 생각해보자. 3.의 경우 Component 전체에서 진입 차수와 진출 차수의 수가 반드시 같아야 한다. 그렇다면 홀도시에 대한 마지막 간선 방향성은 어떻게 처리할까? 여기서 놀라운 솔루션이 등장해버린다..

  "홀도시끼리 겹치지 않게 두 개씩 짝지어 이은 다음, 오일러 회로 및 경로를 구한다."

  이 의미를 다시 곱씹어보자. "진입 차수와 진출 차수가 같다."

  오일러 경로는 진입 차수와 진출 차수의 차이가 정확히 1일 때 사용할 수 있으며,

  오일러 회로는 진입 차수와 진출 차수가 같아야 사용할 수 있다.

  그렇다면 홀도시를 두 개씩 짝지어버리면 어떻게 될까?

  바로 모든 홀도시에 대해 진입 차수와 진출 차수를 같게하거나 정확히 차이를 1로 만들 수 있다. 다시 [Greedy 접근]을 생각해보면 홀도시는 짝도시를 위해 방향을 조절해야만 한다. 그렇다면 오일러 회로 및 경로를 이루기 위해서는 진입 차수와 진출 차수의 차이가 1과 같거나 없어야 한다. 그것을 홀도시를 이음으로써 조건을 강제시키는 것이다. 그렇다면 홀도시끼리 도로를 만든 것과 다름이 없기 때문에, 나중에 답을 도출할 때 이를 반드시 제거하며 출력해야 한다.

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int adj[200][200],fadj[200][200], deg[200];
bool vi[200];
vector<int> c, component;
vector<vector<int>> ans;
void labeling(int u) {
	vi[u] = 1;
	if(deg[u] % 2)
		component.push_back(u);
	for(int v = 0; v < 200; v++)
		if (adj[u][v] && !vi[v])
			labeling(v);
}
void dfs(int u) {
	for(int v = 0; v < 200; v++)
		if (adj[u][v]) {
			adj[u][v]--;
			adj[v][u]--;
			dfs(v);
		}
	c.push_back(u);
}
int main() {
	int t,n,m,u,v,i,j,k,cnt,f;
	scanf("%d", &t);
	while (t--) {
		memset(adj, 0, sizeof adj);
		memset(fadj, 0, sizeof fadj);
		memset(deg, 0, sizeof deg);
		memset(vi, 0, sizeof vi);
		cnt = 0;
		scanf("%d%d", &n, &m);
		for (i = 0; i < m; i++) {
			scanf("%d%d", &u, &v);
			u--, v--;
			adj[u][v]++;
			adj[v][u]++;
			deg[u]++;
			deg[v]++;
		}
		for (i = 0; i < n; i++)	cnt += !(deg[i] % 2);
		for (i = 0; i < n; i++) {
			if (!vi[i]) {
				labeling(i);
				for (j = 0; j + 1 < component.size(); j += 2) {
					u = component[j], v = component[j+1];
					adj[u][v]++, adj[v][u]++;
					fadj[u][v] = fadj[v][u] = 1;
					deg[u]++, deg[v]++;
				}
				component.clear();
			}
		}
		memset(vi, 0, sizeof vi);
		for (i = 0; i < n; i++) {
			if (!vi[i] && deg[i] % 2) {
				dfs(i);
				ans.push_back(c);
				c.clear();
			}
		}
		for (i = 0; i < n; i++) {
			if (!vi[i] && deg[i] % 2 == 0) {
				dfs(i);
				ans.push_back(c);
				c.clear();
			}
		}
		printf("%d\n", cnt);
		for (vector<int>& a : ans) {
			for (i = a.size() - 1; i >= 1; i--) {
				u = a[i], v = a[i - 1];
				if (fadj[u][v] || fadj[v][u]) {
					fadj[u][v] = fadj[v][u] = 0;
					continue;
				}
				printf("%d %d\n", u + 1, v + 1);
			}
		}
		ans.clear();
	}
	return 0;
}

  이 문제가 어렵고 참신한 이유는

1. 여러 Component 존재 가능성

2. Greedy 접근

3. 문제 내용과 동치 관계를 가지고 있는 알고리즘 활용(오일러 회로, 경로)

4. 가짜 간선 생성 및 제거 요구

  문제를 읽고 도저히 알 수가 없어, Editorial을 읽고 소스를 작성했다. 어렵다..