백준 2668 c++ "숫자고르기" -PlusUltraCode-

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

 

 

[필자 사고]

 

처음 방문한 index를 재 방문 했을 경우를 구현할수 있냐 없냐를 묻는 문제이다.

 

필자는 visited를 int 자료형으로 선언하여 부모index 를 저장하게 구현해났다.

 

조심해야 될점은 중복 방문 될 수 있으니 set으로 중복을 없애주거나 따로 

조건을 추가하여야 된다.

 

아래는 소스코드 자세한 설명이다.

 

DFS 함수 (깊이 우선 탐색)

DFS(int startNum, int parentNum, int count) 함수는 깊이 우선 탐색을 수행하는 핵심 함수입니다.

• 먼저 startNum 노드가 이미 방문된 상태인지 확인합니다.
  • 만약 visited[startNum]이 -1이 아니라면, 즉 방문된 상태라면 두 가지 경우로 나뉩니다:
    • visited[startNum]이 -2이면, 이는 해당 노드가 DFS의 시작점임을 의미합니다. 이때 firstNumber로 설정하고 count를 반환합니다.
    • 그 외의 경우에는 사이클이 발생하지 않았으므로 -1을 반환합니다.
• 방문되지 않은 노드라면 parentNum을 부모 노드로 저장하고, arr[startNum]의 값을 다음 노드로 설정하여 재귀적으로 DFS를 호출합니다.

getResultVector 함수

이 함수는 tank라는 set 자료구조를 사용하여 visited 배열에 기록된 부모 노드들을 모읍니다. 이 과정을 통해 각 DFS에서 추적된 경로들의 시작점들을 저장하게 됩니다.

.GameStart 함수

GameStart()는 실제로 게임을 진행하는 함수입니다.

• 먼저 resultCount는 경로의 총 길이를 카운트합니다. tank는 각 경로의 시작점을 저장하는 집합입니다.
• 1부터 N까지 순차적으로 DFS를 실행하여 각각의 노드에서 출발하는 경로를 탐색합니다. 이때 visited 배열을 매번 초기화하여, 각 DFS가 독립적으로 수행되도록 합니다.
• DFS가 유효한 경로를 탐색하면, getResultVector 함수가 호출되어 탐색된 경로의 부모 노드들이 tank에 저장됩니다.
• 모든 노드에 대해 DFS를 수행한 후, tank에 저장된 노드의 개수와 해당 노드들을 출력합니다

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

vector<int> arr;
int N;

int firstNumber = -1;
vector<int> visited;
int mapCount = 0;
void Input() {
	cin >> N;
	arr.resize(N + 1);
	visited.resize(N + 1, -1);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}


void visitedPrint() {
	for (int i = 1; i <= N; i++) {
		cout << visited[i] << " ";
	}
	cout<<'\n' << "-----------" << '\n';

}

int DFS(int startNum,int parentNum, int count) {
	
	if (visited[startNum] != -1) {
		if (visited[startNum]==-2) {
			visited[startNum] = firstNumber;
			return count;
		}

		else {
			return -1;
		}
	}

	visited[startNum] = parentNum;
	int nextNumber = arr[startNum];
	return DFS(nextNumber,startNum,count+1);

}

void getResultVector(set<int>& tank) {
	for (int i = 1; i <= N; i++) {
		if (visited[i] != -1) {
			tank.insert(visited[i]);
		}
	}
}



void GameStart() {
	int resultCount = 0;

	set<int> tank;
	
	for (int i = 1; i <= N; i++) {
		visited.clear();
		visited.resize(N + 1, -1);
		firstNumber = i;
		int flag = 0;
		flag = DFS(i,-2,1);
		if (flag == -1)continue;
		getResultVector(tank);
		resultCount += flag;
	}

	cout << tank.size() << '\n';
	for (auto o : tank) {
		cout << o << '\n';
	}
}

int main(void) {
	Input();
	GameStart();
}