[백준 17204번] 죽음의 게임 (C++)

문제링크 : https://www.acmicpc.net/problem/17204

17204번: 죽음의 게임

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int n, k, num, cnt = 0;
int arr[150];
vector<bool>check;
int main()
{
	fastio;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	check.resize(n);
	num = arr[0];       //첫 방문 값
	while(!check[num])  //다음 값을 이미 방문했다면 멈춤
	{
		cnt++;          //방문횟수 카운트
		check[num] = true;
		if (num == k)  
		{
			cout << cnt;
			return 0;
		}
		num = arr[num];  //다음 값을 가리킴
	}
	cout << -1;        //다음 값을 이미 방문했으면 무한반복이기에 -1 출력
	return 0;
}

 

먼저 입력받을 배열과 현재 값의 방문 확인을 위한 bool형 벡터를 선언했다.

첫 시작은 0번부터이기에 첫 방문 값또한 배열의 0번째 값이다.

 

무한 반복을 돌리되, 다음 값을 이미 방문했다면 멈추게 조건을 설정한다. 

해당 값의 벡터 배열을 방문 처리하여 벡터배열로 방문 여부를 처리한다.

현재 변수에 현재 변수번째의 배열 값을 할당함으로서 다음 값을 가리키게 한다.

(ex : (0, 1) -> (1, 3) ->(3, 1))

 

무한 반복문을 탈출했다는 것은 이미 방문한 값을 또 방문한 것이므로 (무한 반복이므로 이후의 탐색이 의미가 없다) -1을 출력하고, 탈출하지 못했으면 올바른 값을 찾은 것이다.