[Graph] 백준-11558 The Game of Death 실버4 (Python)

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

11558번: The Game of Death

 

 

풀의

• 각 플레이어가 가리키는 정보를 담을 테이블에 각플레이어가 가리키는 정보를 담아준다.
• 각 플레이어의 부모 테이블을 자기 자신으로 초기화 한다.
• 1번 플레이어부터 가리키는 플레이어를 체크한다.
  • 마지막 플레이어를 발견하기 전에 사이클이 발생하면 사이클이 발생함으로 0을 리턴한다.
  • 마지막 플레이어를 발견하면 이동하 횟수를 리턴한다.

 

코드 (Python)

import sys

def input():
    return sys.stdin.readline().rstrip()

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n = int(input())

for _ in range(n):
    player = int(input())
    nodes = [0] * (player + 1) # 가르키는 정보 테이블
    for i in range(1,player+1):
        nodes[i] = int(input())

    parent = [0] * (player + 1) # 부모 테이블 초기화하기
    # 부모 테이블상에서, 부모를 자기 자신으로 초기화
    for i in range(1, player + 1):
        parent[i] = i

    cycle = False
    check_index = 1
    result = 1

    while(nodes[check_index]!=player):  # 마지막 player 발견할 때 까지
        if( find_parent(parent,check_index) == find_parent(parent,nodes[check_index])): # 플레이어 발견전 사이클 발생
            cycle = True
            break
        else:
            result += 1
            union_parent(parent,check_index,nodes[check_index])
            check_index = nodes[check_index]
        

    if(cycle):
        print(0)
    else:
        print(result)