백준 - 11558: The Game of Death(Kotlin)

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

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

 

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

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

문의는 댓글 바람.

 

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

 

[문제 설명]

간단한 그래프 탐색 문제다. 좋은 문제는 아니다.

우선 문제 조건으로 주어진 사람의 수 N은 1 이상 100,000이하다.

그런데 주어진 문제는 뭐냐? 희현이가 주경이를 걸리게 하고 싶은 경우다.

최소 인원수는 2가 되어야 맞지 않을까?

거기다가 입력 설명으로는 희현이는 1번 주경이는 N번이라고 구체적으로 명시까지 했다.

만약, N이 1이면 희현이는 희현이면서 동시에 주경이가 되나? 말이 안되는 문제.

+ T의 개수 제한도 주지 않았다.

 

[접근 방법]

그냥 1번 희현이부터 그래프 탐색을 했다.

희현이가 가르킬 수 있는 사람은 단 1명.

시간복잡도는 최악의 경우 모든 사람은 다 탐색해야하므로 N * 테스트 케이스의 개수 T => O(N*T)다.

 

fun main() {
    val t = readln().toInt()
    val answer = StringBuilder()
    
    for (noOfTestcase in 1..t) {
        val n = readln().toInt()
        val map = Array(n) { readln().toInt() - 1 }
        val visited = Array(n) { false }

        var currentMovement = 0
        var currentPoint = 0
        visited[currentPoint] = true
        while (currentPoint != n - 1) {
            val nextPoint = map[currentPoint]
            if (visited[nextPoint]) {
                answer.append("0\n")
                break
            }
            visited[nextPoint] = true
            currentMovement++
            currentPoint = nextPoint
        }

        if (currentPoint == n - 1) {
            answer.append("$currentMovement\n")
        }
    }

    println(answer)
}