Willing

1. 문제 / 난이도 : Gold Ⅴ

www.acmicpc.net/problem/2668

2. 풀이 및 코드 설명

단순히 그래프의 순환을 찾아서 출력하는 문제. 순환을 찾기 -> 해당 순환의 첫노드와 마지막 노드까지를 answer 배열에 넣기 -> 다음 순환 찾기의 반복으로 풀 수 있었다.

(1) 순환 찾기

for (int i = 1; i <= N; i++) {
		if (!visited[i] && !visited[nums[i]]) checkCycle(i); //현재 노드와 연결된 노드 둘 다 아직 방문한 적이 없는 노드라면 checkCycle
		visited[i] = true; //visited 갱신
	}

• 현재 노드와 연결된 노드를 둘 다 보는 이유는 현재 노드는 당연히 방문한 적이 없어야 하고, 연결된 노드가 이미 방문된 노드라면 앞에서 순환 검사를 이미 끝마쳤다는 소리이기 때문

void checkCycle(int node) {
	visited[node] = true; //visited 갱신
	int next = nums[node];
	
    //만일 순환이 발생한다면
	if (visited[next]) { 
		addAnswer(next, node);//순환의 처음과 끝을 가지고 addAnswer수행
		return;
	}
	checkCycle(next); //순환이 발생하지 않으면 연결된 다음 노드로 이동
}

(2) answer배열에 추가하기

void addAnswer(int start, int goal) {
	int current = start;
	answer.push_back(current);
    // 그래프를 타고 다음 노드로 넘어가며 goal과 같은 노드에 다다르기 전까지 answer 배열에 추가
	while (current != goal) {
		current = nums[current];
		answer.push_back(current);
	}
}

3. 전체 코드

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

int N;
int nums[101];
bool visited[101];
vector<int> answer;

void addAnswer(int start, int goal) {
	int current = start;
	answer.push_back(current);
	while (current != goal) {
		current = nums[current];
		answer.push_back(current);
	}
}

void checkCycle(int node) {
	visited[node] = true;
	int next = nums[node];
	
	if (visited[next]) {
		addAnswer(next, node);
		return;
	}
	checkCycle(next);
}


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

	cin >> N;

	for (int i = 1; i <= N; i++) cin >> nums[i];

	for (int i = 1; i <= N; i++) {
		if (!visited[i] && !visited[nums[i]]) checkCycle(i);
		visited[i] = true;
	}

	cout << answer.size()<<'\n';
	sort(answer.begin(), answer.end());
	for (auto& ele : answer) cout << ele << '\n';
}