이 게시글은 기존 게시물

[C++] 백준 1199번 오일러 회로 - 1

의 기본적인 오일러 회로의 경로 구현으로 발생한 백준 1199번 문제의 시간초과를 해결 방법을 위한 게시물입니다.

기본적인 오일러 회로의 개념과 구현은 위 게시글을 참고하시면 감사하겠습니다.

시간 초과

void getEulerCircuit(int here)
{
	for (int i = 0; i < n; i++) {
		if (adj[here][i] > 0) {
			adj[here][i]--;
			adj[i][here]--;
			getEulerCircuit(i);
		}
	}
	ans.push_back(here);
}

우선 이 문제에서 중요한 부분은 위 코드이다.

그리고 여기서 시간초과의 큰 원인이 된다.

이 코드는 호출될 때마다 모든 정점에 대해서 간선이 존재하는지 확인을 하는 과정을 거치는데 이것이 매우 비효율적이다.

왜냐하면 간선을 하나씩 거치면서 지나온 간선을 지우게 되는데 점점 간선의 개수가 감소하여도 매번 모든 정점을 계산하게 될 것이다.

그래서 정점 사이에 간선이 존재하는 경우에만 확인을 하고 함수를 호출하면 가장 간단히 시간을 줄일 수 있는 방법이 될 것이다.

인접 행렬 vs 인접 리스트

정점 사이에 간선이 존재하는 경우만 어떻게 확인을 할까?

기존의 코드는 인접 행렬을 이용하여 구현하여 확인했는데 이를 인접 리스트로 바꾸면 수월하게 해결할 수 있다.

인접 행렬 : adj[a][b] : a에서 b의 간선이 몇개 인지?

인접 리스트 adj[a][0..n] : a에서 시작해서 간선이 존재하는 n개에 대한 도착 정보

ex) adj[1][0] = 1; → 1번 노드에서 간선이 존재하는 0번째 노드는 1이다.