백준 9466번 텀 프로젝

백준 9466번 링크

문제 풀이

Cycle을 찾는다는 점에서 그래프 문제처럼 생겼지만, 그래프 형태가 워낙 단순해서 스택 문제라고 생각해도 될 것 같다. 사실 DFS나 스택이나 뭐... 같은 방식이니 다른 분들과 다 비슷하게 푼 것 같다.

각 vertex는 directed edge를 하나씩만 가지므로 그래프도 단순하게 int형 배열로 선언한다.

visited를 int형으로 선언한 것이 이 문제를 풀 때 유일한 아이디어?라고 할 수 있을 것 같다.

모든 vertex가 연결되어 있지 않은 그래프에서, 모든 vertex에 대해서 DFS를 진행할 때 각 vertex를 방문한 적이 있는지 확인한다. 이때, cnt라는 int형 변수의 값을 1씩 증가시키고, 이번 DFS에서 방문하는 모든 점들의 visited 값은 cnt로 설정한다. 이렇게 하면 몇번째 DFS에서 방문된 vertex인지 확인이 가능하다. Cycle이 있다면 이번 DFS에서 방문했던 점을 다시 방문하게 될 것이다. 즉, visited 값이 같은 vertex에 도착한다면 cycle이 존재하는 것이다.

Cycle이 존재한다고 해서 이번 vertex에서 방문한 점들이 모두 cycle에 속하는 것은 아니다. 예를 들어, 1 - 2 - 3 - 4 - 2 순으로 방문한다면 2 - 3 - 4 - 2 는 cycle이지만, 1은 cycle에 속하지 않는다. 이 경우는 예외처리를 해야한다.

만약 DFS를 진행하다가 visited 값이 다른 vertex에 도착했다면, 이번 DFS에서 방문한 모든 vertex들은 cycle에 속할 가능성이 없다.

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>

using namespace std;

const int MAX_N = 100000;

int n = 0;
int graph[MAX_N + 1];
int visited[MAX_N + 1];

void init(void) {
	memset(visited, 0, sizeof(visited));
}

void getInput(void) {
	cin >> n;

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

int solve(void) {
	int retval = 0;
	int cnt = 1;

	stack<int> st;
	int v;

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			st.push(i);
			visited[i] = cnt;

			v = i;
			while (1) {
				v = graph[v];

				if (!visited[v]) {
					st.push(v);
					visited[v] = cnt;
				}
				else if (visited[v] != cnt) {
					/* every vertex in stack is out of team */
					retval += st.size();

					while (!st.empty()) {
						st.pop();
					}

					break;
				}
				else {
					/* found cycle */
					while (st.top() != v) {
						st.pop();
					}

					st.pop();

					retval += st.size();

					while (!st.empty()) {
						st.pop();
					}

					break;
				}
			}

			cnt++;
		}
	}

	return retval;
}

int main(void) {
	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		init();
		getInput();
		cout << solve() << endl;
	}

	return 0;
}