글 읽기 - C++ 스택으로 구현했습니다. 반례를 못찾겠습니다 ㅠㅠ

gidskql6671 5년 전 0

질문 게시판에 있던 테스트 케이스는 모두 맞다고 뜨고, 혼자서 이것저것 넣어봤는데 도저히 반례를 찾을 수가 없습니다 ㅜㅜ

알고리즘은 스택으로 구현하였는데, 방문했는지 여부를 저장하는 visit 배열에 첫 방문때는 1을 저장하였고, 빠져나오면서 2를 저장하였습니다.

그리고 만약 다음 이동할 곳이 이미 방문한 곳, 즉 visit[arr[cur]]이 1이라면 visit[arr[cur]]에 사이클이 시작하는 곳이라는 뜻으로 3을 저장시켜주고 Check를 1로 두어서, 스택을 빠져나오면서 사이클 시작지점까지 Count++을 하도록 하였습니다.

만약 visit[cur] 이 3이라면 사이클 시작지점에 도달한거니깐 Check를 0으로 만들어서 Count를 올리지 않고 빠져나가도록 하였구요.

디버깅을 돌려봐도, 혼자서 생각을 해봐도 알고리즘 상에는 문제가 없어보이고, 실제로 반례를 찾을 수가 없는데 틀렸다고 나오네요 ㅜㅜ

혹시 어디가 문제인지, 혹은 반례가 있다면 알려주신다면 감사하겠습니다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int arr[100001];
int visit[100001];
int Check = 0;
int Count = 0;
stack<int> s;

void dfs(int start) {
	s.push(start);

	while (!s.empty()) {
		int cur = s.top();
		if (visit[cur] == 0)
			visit[cur] = 1;
		else if (visit[cur] == 1)
			visit[cur] = 2;
		s.pop();


		if (Check == 1) {
			Count++;
			if (visit[cur] == 3) {
				Check = 0;
				visit[cur] = 2;
			}
			continue;
		}

		if (visit[arr[cur]] == 0) {
			s.push(cur);
			s.push(arr[cur]);
		}
		else if (visit[arr[cur]] == 1) {
			Check = 1;
			visit[arr[cur]] = 3;
			s.push(cur);
		}

	}
}

int main() {
	int T, n;

	scanf("%d", &T);

	for (int t = 0; t < T; t++) {
		memset(visit, 0, sizeof(visit));
		memset(arr, 0, sizeof(arr));
		Count = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d", &arr[i]);
		for (int i = 1; i <= n; i++) 
			if (visit[i] == 0)
				dfs(i);
		printf("%d\n", n - Count);
	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.