글 읽기 - 도움 부탁드립니다.

rlawnddnjs12 2년 전 0

제가 작성한 코드는 1부터 입력한 N까지 하나 하나 DFS(i)형태로 들어가서 싸이클이 나올 때까지

index와 value를 각각 다른 큐에 삽입해주고, 싸이클이 되었을 경우 각각 큐에 담겨져있던 값들이 서로 같은 값으로 이루어져있는지 확인해주는 형식으로, 모두 같은 값들로 이루어져있다면 개수를 추가해주고, 우선순위 큐에 i(인덱스)를 넣어주는 형식으로 짰습니다. (같은 값들로 이루어져 있지 않은 경우 바로 다음으로 넘어감)

어디를 잘못 생각했는지 틀렸습니다가 뜨는데,, 아직도 못잡고 있어서 조언 및 도움 부탁드립니다.

#define _CRT_SECURE_NO_WARNINGS
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

// BOJ :: https://www.acmicpc.net/problem/2668

int N, cnt; bool flag;
bool visited[105];
bool checked[105];
int Num[105];

queue<int> q;
queue<int> n_idx;
priority_queue<int> Answer;

void DFS(int idx) {
	visited[idx] = true;
    
	// n_idx 는 index값에 해당
	n_idx.push(idx);
	// q는 value값에 해당
	q.push(Num[idx]);

	// visited[Num[idx]]가 true라는 것은 전에 방문했던 곳을 다시 재방문한다는 뜻 -> 싸이클에 되돌아옴
	if (visited[Num[idx]] == true) {
		while (!q.empty()) {
			// q에 들어가있는 값들을 checked 배열에서 true로 바꿔줌
			int x = q.front(); q.pop();
			checked[x] = true;
		}

		while (!n_idx.empty()) {
			int x = n_idx.front(); n_idx.pop();
			// n_idx에 들어가있는 값이 checked 배열에서 false인 경우 index와 value가 다른 집합을 의미
			if (checked[x] == false) {
				flag = true;
				break;
			}
		}
		return;
	}

	DFS(Num[idx]);
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> Num[i];
	for (int i = 1; i <= N; i++) {
		// idx와 value가 같은 경우 굳이 DFS로 안들어가도 사이클을 가지므로 cnt+1, Answer pq에 푸쉬
		if (i == Num[i]) {
			cnt++;
			Answer.push(-i);
			continue;
		}
		memset(visited, false, sizeof(visited));
		memset(checked, false, sizeof(checked));
		flag = false;
		DFS(i);
		// DFS함수 내에서 flag가 true라는 것은 idx와 val이 다른 집합을 의미하므로 false일 때만 개수 증가 및 idx를 우선순위 큐에 푸쉬
		if (!flag) {
			cnt++;
			Answer.push(-i);
		}
	}
	cout << cnt << "\n";
	while (!Answer.empty()) {
		int ans = Answer.top();
		Answer.pop();
		cout << -ans << "\n";
	}

	return 0;
}

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

문제

문제

출처

ICPC

도움 부탁드립니다.

rlawnddnjs12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말