(백준-17204번) 죽음의게임 - 파이썬

영관·2023년 3월 4일
0

백준문제

목록 보기
1/11
post-thumbnail

문제 분석

백준 S3수준의 문제로 문제가 길지만 결국에는 사람들을 노드로 표현하고 지목하는 사람들을 간선으로 표현한 문제이다.
이 문제에서 구할 것은 보성이가 벌주에 걸리도록 하기 위해서 숫자를 구하면 된다. 보성이의 번호는 주어져 있기 때문에 결국 지목한 대로 그래프를 구현한 후 보성이의 순서를 출력하면 그것이 답이다.

  • 그래프를 구현하여 DFS탐색!

문제 링크
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를 구현하였다.

profile
달인이 되는 그날까지!

0개의 댓글