백준 - 죽음의 게임(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/17204

 

[문제 설명]

김영기와 보성이가 술자리에 참여한다.

N명의 사람들이 게임을 진행한다.

번호는 0번부터 N-1번까지 존재한다.

0번이 M을 외치면 M번째 순회하는 사람이 술을 마신다.

영기는 0번, 보성이는 K번.

보성이게 마시게 하기위해 필요한 숫자의 최솟값은?

 

[접근 방법]

차수가 1인 방향그래프이면서 반사적인 노드가 존재한다.

보성이가 걸리지 않는다면 -1을 출력해야 한다.

그래프 순회 중 반사하여 자기를 지목하는 노드가 걸리면 보성이와는 만날 수 없다.

주의할 점 : 번호는 0번부터 시작

 

[의사 코드]

변수선언 (사람의 수 N, 보성이의 번호 K) = 입력

그래프배열 graph = Array(N) // 배열의 인덱스는 사람의 번호, 값은 해당하는 사람이 가리키는 사람

for (noOfPeople = 0 noOfPeople < N noOfPeople++) {

    graph[noOfPeople] = 가르키는사람번호

}

 

변수선언 M = 0

변수선언 (현재 사람번호 noOfCurrent) = 0

변수선언 (방문여부를 처리할 Boolean형 배열 isVisited) = BooleanArray(N)

// 방문했던 사람을 만나기 전까지는 반복

while (!isVisited[noOfCurrent]) {

   isVisited[noOfCurrent] = true

   M++

   if (graph[noOfCurrent] == K) {

      break

   }

   noOfCurrent = graph[noOfCurrent]

}

 

// K번을 만나면 M을 출력, 못만나면 -1을 출력

if (graph[noOfCurrent] == K) {

   println(M)

} else {

   println(-1)

}

 

[Kotlin 코드]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N,K) = readLine().split(" ").map{it.toInt()}
    // 인덱스는 해당하는 사람, 값은 해당하는 사람이 가리키는 사람
    val graph = IntArray(N)
    repeat(N) { noOfPeople ->
        graph[noOfPeople] = readLine().toInt()
    }

    val isVisited = BooleanArray(N)
    var M = 0
    var noOfCurrent = 0
    while (!isVisited[noOfCurrent]) {
        isVisited[noOfCurrent] = true
        M++
        if (graph[noOfCurrent] == K) {
            break
        }
        noOfCurrent = graph[noOfCurrent]
    }

    when (graph[noOfCurrent]) {
        K -> println(M)
        else -> println(-1)
    }
}