백준 17204 - 죽음의 게임

문제

알고리즘 분류)

• 구현
• 그래프 이론
• 그래프 탐색
• 시뮬레이션

술 게임 중에 있는 "The Game of Death" 라는 게임과 연관된 문제이다

문제풀이에 앞서서 이 문제는 그래프로도 풀수있고 단순히 문제에 따라 구현해서 풀수도 있는 2가지 방법이 있다고

생각했는데 마침 알맞게 알고리즘분류가 설정되어 있었다

풀이

DFS 풀이)

각 사람은 지목한 사람이 한명씩 있다 -> 단방향 간선
N명의 사람이 있으므로 -> N*N개의 간선정보 행렬
을 추출해낼 수 있으므로 dfs로 풀수 있다

예제 입력1)

5 3
1
3
2
1
4

n번째 행 사람이 가리키는 사람m은 1로 표시한다

[[0, 1, 0, 0, 0],
 [0, 0, 0, 1, 0],
 [0, 0, 1, 0, 0],
 [0, 1, 0, 0, 0],
 [0, 0, 0, 0, 1]]

영기는 0번이므로 dfs(0)부터 실행해준다
방문한 사람은 visited[]=1로 방문처리를 해준다
보성이의 번호로 dfs가 실행되었다면 -> count 출력
이미 방문한 사람을 또 방문한다면 사이클이 생긴것이므로 보성이가 지목될 수 없다 -> -1 출력

소스코드

python)

• DFS풀이

  import sys
  global cnt
  cnt = 0
  
  def dfs(v):
      global cnt
      if v == bosung:
          print(cnt)
          return
      visited[v] = True
      cnt+=1
      for i in range(N):
          if array[v][i]:
              if visited[i]:
                  print(-1)
                  return
              dfs(i)
  
  N, bosung = map(int, input().split())
  array = [[0 for col in range(N)] for row in range(N)]
  visited = [0]*N
  for i in range(N):
      person = int(input())
      array[i][person] = 1
  
  dfs(0)

• 시뮬레이션 풀이
  예제 입력은 위와 동일하다
  2차원 배열에
  [[0번사람,지목한사람] , [1번사람,지목한사람] , [2번사람,지목한사람] ... [N번사람,지목한 사람]]
  과 같이 배열을 선언해준다

  [[0, 1], [1, 3], [2, 2], [3, 1], [4, 4]]

  while문을 통해 반복횟수<N 을 만족할 때 까지 반복한다.
  N을 넘어가면 사이클이 발생했다는 의미이므로 -1을 출력한다
  그렇지않으면 N번째 배열의 index:1은 다음 지목될 사람으로 루프를 돈다
  그리하여 반복문이 돌아간 횟수만큼 정답을 출력하면 된다

  import sys
  N, bosung = map(int, input().split())
  array = [[row for col in range(2)] for row in range(N)]
  for i in range(N):
      person = int(input())
      array[i][1] = person
  num=0
  cnt=1
  while cnt<=N:
      num = array[num][1]
      if num == bosung:
          print(cnt)
          break
      cnt+=1
  
  if cnt>N:
      print(-1)