[백준 17204번] 죽음의 게임 - python

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

📌 문제 탐색하기

목표

• 0번부터 시작해서 보성이의 번호 K까지 순서가 이어질 수 있는지 판단한다.
• 순서가 이어질 수 없다면 -1을, 이어질 수 있다면 걸리는 횟수를 출력한다.

입력값

• 첫째 줄에 게임에 참여하는 사람의 수 N과 보성이의 번호 K가 공백을 두고 주어진다. (3 ≤ N ≤ 150, 1 ≤ K ≤ N - 1)
• 둘째 줄부터 N줄에 걸쳐 i번 사람이 지목하는 사람의 번호 $a_i$가 주어진다. (0 ≤ i ≤ N - 1, 0 ≤ $a_i$ ≤ N - 1)
• ex)
• 5 3 1 3 2 1 4

출력값

• 영기가 말해야하는 가장 작은 양의 정수 M을 출력한다.
• 보성이가 마지막에 지목되지 못한다면 -1을 출력한다.
• ex)
• 2

📌 코드 설계하기

해결 아이디어

• 어제와 비슷한 그래프 문제다. dfs를 배웠으니 여기서도 dfs를 적용해 볼 수 있다고 생각했다.
• 하나의 사이클이 완료가 되면 보성이가 지목되지 않았다는 뜻이므로 -1을 출력한다.
• 사이클이 생기는 도중 보성이의 번호가 지목된다면 즉시 얼마나 많은 사람을 거쳤는지 반환해주고 이를 출력한다.

📌 정답 코드

import sys

def dfs(n, k, cnt):
    used[n] = True
    nextnode = arr[n]
    cnt += 1
    if nextnode == k:
        return cnt
    if not used[nextnode]:
        return dfs(nextnode, k, cnt)

n, k = map(int, sys.stdin.readline().split())

arr = []
cnt = 0
for i in range (n):
    arr.append(int(sys.stdin.readline()))
    
used= [False] * (n+1)    
print(dfs(0, k, cnt) or -1)

시간 복잡도 구해보기

• 입력
  • 배열을 입력하는 과정이므로 O(N)
• for문
  • len(arr)만큼 for문을 돈다. → O(N)
  • 이미 사용된 노드는 다시 처리되지 않는다.

최종 시간 복잡도: O(N)

코드 정리

for i in range (n):
    arr.append(int(sys.stdin.readline()))

좀더 파이썬스럽게 코드를 정리해보자. 해당 arr를 삽입하는 과정은 다음과 같이 리스트 컴프리헨션 방식으로 축약될 수 있다.

arr = [int(sys.stdin.readline()) for _ in range(n)]

길이가 n인 리스트를 한 번에 생성할 수 있고 해당 실행이 끝나면 arr에 값들이 모두 추가되어 완료된다. 속도 측면에서도 파이썬 내부 최적화로 인해 리스트 컴프리헨션 방식이 약간 더 빠르다고 한다.