[백준 11558번] The Game of Death 풀이

11558번: The Game of Death

 

T개의 테스트 케이스를 받아 처리해야 하므로 T개만큼 for문으로 돌려준다.

각 테스트 케이스마다 플레이어 명수 N을 입력 받고, 벡터의 1~N 인덱스에 각 플레이어가 지목한 플레이어를 저장한다. 

(벡터의 크기를 N+1로 지정한 이유는 1인덱스에는 플레이어 1이 지목한 사람,.. N인덱스에는 플레이어 N이 지목한 사람을 맞추어 저장하기 위함이다. 0부터 하면 또 헷갈릴테니 벡터의 0 자리는 비워둔다.)

 

첫번째 플레이어 1이 가르키고 있는 플레이어는 v[1]이며, 이를 p에 저장한다.(p=v[1])

이 떄, 지목당한 p가 지목하고 있는 사람은 v[p]이므로, 다음 번부터 계속해서 p=v[p]가 된다. 

만약 p가 N번째 사람이라면, N번째 사람이 주경이 이므로 k가 최소 cnt가 될 때 주경이가 걸리게 할 수 있다.

만약 지목한 횟수 cnt가 전체인원 N명 보다 커진다면, 이는 서로를 가리키는 동안 주경이를 찾지 못한다는 의미이므로 0을 출력한다.

 

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

int main() {

    int T;
    scanf("%d", &T);

    for (int i=0; i<T; i++) {
        
        int N;
        scanf("%d", &N);

        vector<int> v(N+1);
        for (int i=1; i<=N; i++)
            scanf("%d", &v[i]);

        int cnt = 1;
        int p = v[1];
        while (p != N && cnt <= N) {
            p = v[p];
            cnt++;
        }

        if (cnt > N) cnt = 0;
        printf("%d\n", cnt);
    }
    return 0;
}