[파이썬/Python] 백준 17204번: 죽음의 게임

숨·2024년 7월 19일

알고리즘 문제 풀이

목록 보기

37/105

📌 문제 : 백준 17204번

📌 문제 탐색하기

N : 게임에 참여하는 사람의 수 ( $3 ≤ N ≤ 150$ )
K : 보성이 번호 ( $1 ≤ K ≤ N - 1$ )
i : 지목하는 사람의 번호 ( $0 ≤ i ≤ N - 1$ )
$a_{i}$ : i번 사람이 지목하는 번호 ( $0 ≤ a_{i} ≤ N - 1$ )

✅ 입력 조건
1. N, K 입력
2. N번 반복해 i번 사람이 지목하는 사람의 번호 입력
3. 자기 자신 지목 가능
✅ 출력 조건
1. 보성이가 걸리도록 영기가 말해야 하는 가장 작은 양의 정수 M 출력
2. 보성이가 걸리지 않으면 -1 출력

게임의 참여하는 N명의 사람은 0부터 N-1까지의 번호를 하나씩 가진다.
N번 반복해 얻은 $a_{i}$ 는 0번부터 시작해서 각각 몇 번을 지목했는지를 뜻한다.
서로 지목하면서 숫자를 하나씩 말하다가 M을 말하게 될 사람을 찾는 문제이므로, i와 $a_{i}$ 는 연결 정보를 의미한다.
이를 그래프에 저장하여 연결 노드를 탐색한다.

BFS를 돌면서 연결 노드를 탐색하면서 탐색한 노드 수를 카운트한다.
탐색할 다음 노드 번호가 K라면 그 때의 카운트된 수를 출력으로 내보내면 된다.
아니라면 계속 카운트하면서 BFS 탐색을 수행한다.
만약 탐색이 종료되어도 K 노드가 나오지 않았다면 어떠한 방법으로도 보성이가 걸리지 않음(즉, 연결되지 않음)을 의미하므로 -1를 출력한다.

가능한 시간복잡도

그래프 저장 → $O(N)$
BFS 수행 → $O(N)$

최종 시간복잡도
$O(N)$ 으로,
최악의 경우, N이 최대 150일 때도 1초 내로 계산이 가능할 것 같다.

알고리즘 선택

그래프에 연결 정보 저장하고 원하는 노드가 나올 때까지 BFS를 수행하면서 카운트한다.

📌 코드 설계하기

BFS 정의
1-1. 방문 처리
1-2. 큐가 빌 때까지 반복
1-3. 해당 노드 연결 정보 확인
1-4. 방문 안했다면 방문 처리
N, K 입력
그래프 저장
방문 리스트 정의
BFS 수행
원하는 결과 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# BFS 정의
def BFS(x):
    queue = deque([x])
    visited[x] = 1
    M = 0

    while queue:
        y = queue.popleft()

        if graph[y] == K:
            return M + 1  # K에 도달한 시점의 M 값 반환
        next_node = graph[y]
        if not visited[next_node]:
            visited[next_node] = 1
            queue.append(next_node)
            M += 1
    return -1


# N, K 입력
N, K = map(int, input().split())

# 그래프 저장
graph = [int(input()) for _ in range(N)]

# 방문 리스트 정의
visited = [0] * N

# BFS 수행
result = BFS(0)

# 원하는 결과 출력
print(result)