[알고리즘] 백준 9466번: 텀 프로젝트 (C++)

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

이번 문제는 계속 시간 초과가 나서 계속 뜯어고칠수록 코드를 점진적으로 진화시키는 기분이 들었다.

이번 문제의 키워드는 '사이클의 유무 판단'이다.

---

첫 시도

첫 시도에서는 각 노드마다 for문을 통해 '이 노드는 사이클을 형성하는가?'의 여부를 따졌었다.

그 여부는 백트래킹을 통해 두 개의 인자를 받아들여 코드를 짰다.

하지만, 노드의 최대 개수 100,000개가 주어지고, 100,000개 전체가 하나의 사이클을 형성한다고 할 때 (Worst Case),

시간 복잡도가 (n^2)로 시간 초과가 발생한다.

>> 70% 후반대까지 올라갔음.

#include <iostream>
using namespace std;
#define MAX 100000 + 1

int arr[MAX];
bool visited[MAX];
int cnt;

void backTrack(int startNode, int value) {
	if (arr[startNode] == value) {
		cnt--;
		return;
	}

	if (!visited[startNode]) {
		visited[startNode] = 1;
		backTrack(arr[startNode], value);
		visited[startNode] = 0;
	}
}

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

	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int n;
		cin >> n;
		cnt = n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}

		for (int i = 1; i <= n; i++) {
			backTrack(i, i);
		};

		cout << cnt << '\n';
	}
	return 0;
}

---

두 번째 시도

각 노드 별로 따지는 건 시간을 많이 잡아먹겠구나 싶어서 어떤 한 노드를 탐색할 때, 그 노드로부터 사이클이 발생되는 노드들은 다음에 탐색을 하려 할 때, 이미 사이클이란 걸 알려줌으로써 사이클에 포함된 노드는 탐색을 하지 않으며 시간을 줄이려 했다.

그래서, 스택을 통해서 백트래킹을 구현해보았다.

(시간을 줄이려고 불필요한 리셋 함수들도 다 없애보았지만 시간 초과가 난다.)

>> 82%까지 올라갔음.

 

(visited는 단순 방문 배열, check는 사이클을 발생시키는 노드를 담은 배열)

#include <iostream>
#include <stack>
#define MAX 100000 + 1
using namespace std;

int arr[MAX];
int check[MAX];
bool visited[MAX];
int T;
stack<int> s;
int result;

void backTrack(int v, int findv) {
	// 스택을 이용하여 사이클의 여부를 따짐.
	s.push(arr[v]);

	if (!s.empty() && s.top() == findv) {
		s.pop();
		while (!s.empty()) {
			//cout << s.top() << '\n';
			check[s.top()] = 1;
			s.pop();
			result--;
		}
		//cout << '\n';
		return;
	}

	if (!visited[arr[v]]) {
		visited[arr[v]] = 1;
		backTrack(arr[v], findv);
		visited[arr[v]] = 0;
	}
}

void resetS() {
	while (!s.empty()) {
		s.pop();
	}
}

void resetCheck(int value) {
	for (int i = 1; i <= value; i++) {
		check[i] = 0;
	}
}

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		int n;
		cin >> n;
		result = n;

		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}

		for (int i = 1; i <= n; i++) {
			if (!check[i] && !visited[i]) {
				visited[i] = 1;
				s.push(i);
				backTrack(i, i);
				visited[i] = 0;
			}
			resetS();
		}


		cout << result << '\n';
		resetCheck(n);
	}

	return 0;
}

---

솔루션

두 번째 시도까지도 시간 초과가 나서 더 보완을 하되 어떻게 해야 할까를 생각해보았는데 '사이클을 발생시키지 않는 노드' 또한 신경을 써야 할 거 같았다.

예를 들어 1부터 n까지 탐색을 하는데 1이 사이클을 발생시키지 않는다고 했을 때,

4라는 노드에서 1을 향하고 있다고 했을 때, 1은 사이클을 발생시키지 않으니 4도 사이클을 발생시키지 않음을 코드로 표현해야겠다고 생각했다.

>> 그렇게 되면 탐색해야 할 노드도 줄어든다.

(+참고 https://ongveloper.tistory.com/167)

참고했던 블로그의 필자 분도 나와 마찬가지로 82%에서 시간 초과가 났었다.

 

참고한 코드가 이해는 갔으나 for문의 사용방법이나 여러모로 얻어낼 게 많다고 생각해서 여러 번 봐야 할 거 같다.

1) 백트래킹을 시작하자마자 바로 해당 노드의 방문을 체크한다.

 

2-1) 해당 노드가 가리키는 노드가 방문되어있지 않다면 재귀를 통해 백트래킹을 한다.

 

2-2) 재귀가 끝나면 백트래킹 끝나면서 check에 다음 노드들을 사용했다고 해준다.

 

3-1) 방문이 되었는데 check에 담겨있지 않다는 것은 지금 가리키는 노드가 맨 처음 시작 노드라는 뜻이다.

3-1) + 사이클을 처리해주고, 사이클에 해당하는 노드들도 check에 담는다.

 

3-2) 특이한 for문을 통해 사이클을 형성하는 노드의 개수를 cnt 해준다.

 

>> 즉, 이 코드에서 check의 역할은 해당 노드가 사이클을 형성하든 형성하지 않든 할 일을 다 했으니 더 이상 사용하지 않는 노드들을 담는다는 의미로 쓰일 수 있다.

(visited 즉각 방문, check 최종 방문 느낌?)

#include <iostream>
#include <stack>
#define MAX 100000 + 1
using namespace std;

int arr[MAX];
int check[MAX];
bool visited[MAX];
int T;
int result;
int cnt;

void backTrack(int node) {
	visited[node] = 1;
	int next = arr[node];

	if (!visited[next]) {
		backTrack(next);
	}
	else if (!check[next]) {
		// 이 조건으로 온다는 것은 사이클을 발생시킨다는 의미
		// check[next]에 1이 있다는 것은 사이클이 아닌 끝이 존재한다는 의미

		// 1-3-5라는 사이클이 있다고 할 때
		for (int i = next; i != node; i = arr[i]) {
			// 여기서 3과 5를 카운트
			cnt++;
		}
		// 여기서 1을 카운트한다는 의미
		cnt++;
	}
	check[node] = 1;
	//cout << node << ' ';
}

void resetCheck(int value) {
	for (int i = 1; i <= value; i++) {
		check[i] = 0;
	}
}

void visitedReset(int value) {
	for (int i = 1; i <= value; i++) {
		visited[i] = 0;
	}
}

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		int n;
		cin >> n;
		result = n;
		cnt = 0;

		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}

		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				backTrack(i);
				//cout << '\n';
			}
		}

		cout << result - cnt << '\n';

		resetCheck(n);
		visitedReset(n);
	}

	return 0;
}

---

무조건 업 솔빙 해야 할 문제라고 느꼈다.

사이클을 처리하는 것부터 사이클을 아닌 노드들까지 처리 함으로써 시간을 줄이고, for문을 저렇게 사용함으로써 재귀나 스택을 이용하지 않는다는 점에서 이 코드에는 배울 것이 많다고 느꼈다. 업 솔빙을 제외하고도 시간 날 때마다 들여다보면 좋을 코드 같다. 배울 센스가 많다.