백준 S3수준의 문제로 문제가 길지만 결국에는 사람들을 노드로 표현하고 지목하는 사람들을 간선으로 표현한 문제이다.
이 문제에서 구할 것은 보성이가 벌주에 걸리도록 하기 위해서 숫자를 구하면 된다. 보성이의 번호는 주어져 있기 때문에 결국 지목한 대로 그래프를 구현한 후 보성이의 순서를 출력하면 그것이 답이다.
문제 링크
https://www.acmicpc.net/problem/17204
문제
import sys
from collections import deque
input = sys.stdin.readline
# 보성이가 벌주를 마시기 위해 영기가 불러야 하는 가장 작은 양의 정수
# n: 게임에 참여하는 사람의 수, k: 보성이의 번호
n, k = map(int, input().strip().split())
# i번 사람이 지목하는 사람의 번호(0 ~ 4)
graph = [[] for _ in range(n)]
for i in range(n):
node = int(input().strip())
graph[i].append(node)
visited = [False] * (n)
cnt = 0
def dfs(start):
global cnt
stack = deque()
stack.append(start)
visited[start] = True
while stack:
now = stack.pop()
# 보성이의 번호가 걸린다면
if now == k:
return cnt
else:
cnt += 1
for i in graph[now]:
if visited[i] == False:
stack.append(i)
visited[i] = True
return -1
print(dfs(0))
dfs구현 시 재귀를 이용하려 했으나 보성이의 순서를 순차적으로 구하기 위해서는 재귀의 매개변수로 순서변수인 cnt를 전달해야하는 불편함이 존재했다.
그렇기 때문에 stack을 이용하여 dfs를 구현하였다.