(C++) BOJ/백준 1199 - 오일러 회로

문제 출처 : BOJ 1199 - 오일러 회로 https://www.acmicpc.net/problem/1199

1199번: 오일러 회로

 

정점의 수와 인접행렬의 정보가 주어지면, 오일러 회로 경로를 출력하는 문제이다.

 

3시간동안 시간 초과의 늪에 빠져있다가 드디어 빠져나왔다.

 

아래에 있는 코드가 내가 처음 짠 코드이다.

시간 초과인데 큰 걸 고칠 생각은 안하고 찔끔찔끔 고치다가 위같은 결과물이 나왔다.

#include <iostream>
#include <vector>
using namespace std;

int n, cnt = 0, arr[1001][1001], lines[1001];

void dfs(int cur) {
	for (int i = 1; i <= n; i++) {
		while (arr[cur][i]) {
			arr[cur][i]--;
			arr[i][cur]--;
			dfs(i);
		}
	}
	cout << cur << ' ';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int sum = 0;
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			sum += arr[i][j];
		}
		if (sum % 2) {
			cout << "-1\n";
			return 0;
		}
		cnt += sum;
	}

	cnt /= 2;
	dfs(1);
	cout << '\n';

	return 0;
}

arr[][] 배열에 행렬 정보를 받고, 이를 그대로 dfs에 적용시켜 1부터 n까지 탐색하면서 간선의 정보를 찾았다.

 

도대체 무엇이 잘못된건지 생각해보다가 평소에 배열보다 더 자주쓰던 리스트, 즉 벡터를 써보기로 했다.

 

최종 코드

#include <iostream>
#include <vector>
using namespace std;

int n, cnt = 0;

int arr[1001][1001];
vector<int> v[1001];
vector<int> ans;

void dfs(int cur) {
	while (!v[cur].empty()) {
		if (arr[cur][v[cur].back()]) {
			arr[cur][v[cur].back()]--;
			arr[v[cur].back()][cur]--;
			dfs(v[cur].back());
		}
		else v[cur].pop_back();
	}
	cout << cur + 1 << ' ';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j]) v[i].push_back(j);
			sum += arr[i][j];
		}
		if (sum % 2) {
			cout << "-1\n";
			return 0;
		}
	}

	dfs(0);
	cout << '\n';
	return 0;
}

위의 틀린 코드를 전부 갈아엎고 처음부터 다시 썼다.

arr[][] 배열에는 간선 개수에 대한 정보만 저장해두고,

dfs에서는 벡터 v에 저장된 정보를 이용해서 그래프를 탐색하는 방식이다.

 

dfs() 함수에서 v[cur]를 탐색할 때 back() 함수를 쓴 것은,

처음에 for (int i = 0; i < v[cur].size(); i++) 이런 식으로 짰다가

arr[cur][v[cur][i]] == 0일 때 v[cur][i]를 어떻게 쉽게 삭제할지 고민하다가 저렇게 되었다.

 

이렇게 간단하게 풀 수 있는 문제였는데 문제에서 인접 행렬로 주어지다보니까 눈이 돌아버린 것 같다.

 

오늘 2차 백신을 맞고 와서 몸이 너무 안좋았는데

정답률이 무려 12.828%인 문제를 풀어서 기분이 좋아졌다.