[백준] 죽음의 게임

문제보기 - https://www.acmicpc.net/problem/17204

문제명    - 순열 사이클

난이도    - S3

문제유형 - 그래프이론

풀이일자 - 25.03.16

 

📌 문제 탐색하기

• N명의 학생이 원형으로 앉아있고 0번 학생부터 시작하여 각 학생이 가리키는 다음 학생 번호에 따라 정해짐
  
  • 1 ≤ N ≤ 100 (학생 수)
• 특정 번호(K) 학생에게 도달하면 게임이 끝남
  •  0 ≤ K < N (목표 학생 번호)
• K번 학생에게 도달하기 위한 최소 이동 횟수를 구하는 문제

🛠 시간복잡도 확인

• 각 학생이 하나의 노드, 이동이 간선이 되는 단방향 그래프 탐색 문제임
• 최대 학생 수가 100명이므로 BFS(너비 우선 탐색) 가능! -> O(N)

 

📌 코드 설계하기

1. BFS를 사용하여 최소 이동 횟수 계산 함수 생성하기(import deque)
   • visited 리스트로 방문 여부 체크
     • visited = [False] * N
   • queue를 사용하여 0번 학생부터 탐색
     
     • queue = deque([(0, 0)])
   • count를 증가시키면서 K번 학생에 도달하면 정답 반환
2. N,K 입력값을 받기
3. K번 학생을 찾으면 결과 출력하고 찾지 못한 경우 -1 출력하기

 

📌 정답 코드(1회차)

import sys
from collections import deque

# 1. BFS를 사용하여 최소 이동 횟수 계산 함수 생성하기
def death_game(N, K, moves):
    visited = [False] * N 
    queue = deque([(0, 0)])  # (현재 학생 번호, 이동 횟수)
    visited[0] = True
    
    while queue:
        current, count = queue.popleft()

        if current == K:  # 현재 학생이 K번 학생이면 이동 횟수 반환
            return count
        
        next_student = moves[current]
        if not visited[next_student]:
            visited[next_student] = True
            queue.append((next_student, count + 1))
            
    return -1  # K번 학생을 찾지 못한 경우

# 2. N,K 입력값을 받기
N, K = map(int, sys.stdin.readline().split())
moves = [int(sys.stdin.readline().strip()) for _ in range(N)]

# 3. 결과 출력
print(death_game(N, K, moves))