[그래프 탐색] 죽음의 게임(17024)

문제 설명

 

새내기들과 같이 술을 마시게 된 영기와 보성이는 분위기가 가라앉을 때쯤 The Game of Death라고 불리는 죽음의 술게임을 제안한다.

죽음의 게임의 룰은 간단하다.

게임에 참여하는 N명의 사람들은 원탁에 둘러앉게 된다. 게임을 시작하는 사람은 0번, 그 오른쪽 사람은 1번, 그 오른쪽은 2번, N-1번의 오른쪽 사람은 다시 0번이 된다.

0번이 "신난다! 아싸 재미난다! 아싸 더 게임 오브 데! 스!"라고 외침과 동시에, 모든 사람들은 각각 테이블에 둘러앉은 사람들 중 한 명을 지목한다. 그러고 나서 0번은 임의의 양의 정수 M을 외친다.

그 다음, 0번은 "1"이라고 말한다. 이때 "1"이라고 말한 사람이 지목한 사람은 "2"라고 말하고, "2"라고 말한 사람이 지목한 사람은 "3"이라고 말하고, 같은 방식으로 반복해 M까지 말하게 된다. 이때 마지막으로 M이라고 말한 사람이 지목한 사람은 벌주를 마시게 된다.

새내기에게 벌주를 마시게 하기에는 죄책감이 들었던 영기는 동기인 보성이를 공격하기로 결심했다. 게임 참여자들 간에 지목을 완료한 상태가 주어질 때, 보성이가 벌주를 마시기 위해 영기가 불러야 하는 가장 작은 양의 정수 M을 보성이 몰래 귀띔해 주도록 하자.

김영기는 게임을 제안하였기에 자연스럽게 0번이 된다.

---

입력

첫 번째 줄에 게임에 참여하는 사람의 수 N(3 ≤ N ≤ 150)과 보성이의 번호 K(1 ≤ K ≤ N - 1)가 공백을 두고 주어진다.

두번째 줄부터 N줄에 걸쳐 i(0 ≤ i ≤ N - 1)번 사람이 지목하는 사람의 번호 ai(0 ≤ ai ≤ N - 1)가 주어진다. 자기 자신을 지목하는 경우도 존재할 수 있다.

 

출력

영기가 말해야 하는 가장 작은 양의 정수 M을 출력한다. 만약 어떤 방법으로도 보성이가 걸리지 않는다면 -1을 출력한다

 

---

문제 풀이

 

전형적인 그래프 탐색 문제이다. DFS/BFS 알고리즘을 통해 쉽게 풀 수 있다.

시간 복잡도는 O(v+e)로 정점의 개수+간선의 개수의 합이다.

1. 입력받는 인덱스를 정점(v1), 값은 해당 정점이 가리키는 정점(v2)으로 1차원 배열(graph) 생성
2. stack/deque에 1에서 생성한 0번째 값을 push
3. DFS/BFS 알고리즘 수행, 다음 정점으로 이동시 count 증가
     3-1. 다음 정점이 보성이의 번호(K)와 같다면 break

from collections import deque
import sys
input = sys.stdin.readline
inputData = list(map(int, input().split(' ')))
n, k = inputData[0], inputData[1]
graph = [0 for _ in range(n)]
answer, findCount = 0, 0
seen = set()
stack = [] #DFS
# q = deque([]) #BFS

for i in range(n): #1
  e = int(input())
  graph[i] = e

stack.append(graph[0]) #2
# q.append(graph[0])

while stack: #3
  nextPos = stack.pop()
  #nextPos = stack.popleft()
  findCount +=1

  if nextPos == k: #3-1
    answer = findCount
    break
  for i in range(len(graph)):
    if nextPos not in seen:
      stack.append(graph[nextPos])
      seen.add(nextPos)

if answer:
  print(answer)
else:
  print(-1)

---

결과 및 후기

그래프 탐색 복습으로 가벼운 문제를 풀었다. 문제도 내가 알고있는 술 게임이라 한 번에 이해할 수 있어서 재밌는 문제였다☺️

오늘은 반복문으로 DFS/BFS를 구현했지만 다음에는 재귀문으로 구현해봐야겠다~!