백준 14248 점프 점프 Kotlin (dfs)

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

14248번: 점프 점프

문제

영우는 개구리다 개굴개굴개굴

영우는 지금 n개의 돌이 일렬로 놓여있는 돌다리에 있다. 그리고 돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있는데, 이때 돌다리 밖으로 나갈 수는 없다.

영우는 이 돌다리에서 자기가 방문 가능한 돌들의 개수를 알고 싶어한다. 방문 가능하다는 것은 현재위치에서 다른 돌을 적절히 밟아 해당하는 위치로 이동이 가능하다는 뜻이다.

현재 위치가 주어졌을 때, 영우가 방문 가능한 돌들의 개수를 출력하시오.

입력

첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000)

다음 줄에는 출발점 s가 주어진다.(1≤s≤n)

출력

영우가 방문 가능한 돌들의 개수를 출력하시오.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

간단한 dfs 문제이다.

각 정점마다 한 번씩 밖에 들리지 않으므로 n번의 탐색으로 끝난다.

물론 bfs로도 가능하다.

시작점에서부터 현재 칸에 적힌 수만큼 좌, 우로 이동할 수 있는지 확인하고(배열의 범위를 벗어나지 않는지) 이동하기를 반복한다.

방문한 칸은 재방문하지 않도록 처리한다.

주의할 점은 '이 숫자가 적혀있는 만큼 점프'의 의미는 2가 적혀있으면 좌우로 1칸, 2칸을 점프하는 게 아니라 2칸만 점프하는 것,

input을 그냥 br.readLine().split(' ')으로 처리하면 numberFormatException이 뜬다....

아마 입력에 불필요한 공백이 들어가 있거나 한 거 같다.

따라서 StringTokenizer로 입력을 받자.

이런 입력은 좀... 싫다.

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var graph: IntArray
var answer = 0
fun dfs(cur: Int) {
    var jump = graph[cur]
    graph[cur] = 0
    answer++

    val left = cur - jump
    val right = cur + jump
    if (left in graph.indices && graph[left] > 0) {
        dfs(left)
    }
    if (right in graph.indices && graph[right] > 0) {
        dfs(right)
    }
}

fun main() = System.out.bufferedWriter().run {
    //input
    var tk = StringTokenizer(br.readLine())
    val n = tk.nextToken().toInt()
    tk = StringTokenizer(br.readLine())
    graph = IntArray(n){tk.nextToken().toInt()}
    tk = StringTokenizer(br.readLine())
    val s = tk.nextToken().toInt()
    //solve
    dfs(s - 1)
    //output
    write("$answer")
    close()
}