https://www.acmicpc.net/problem/14248
[문제]
영우는 개구리다 개굴개굴개굴
영우는 지금 n개의 돌이 일렬로 놓여있는 돌다리에 있다. 그리고 돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있는데, 이때 돌다리 밖으로 나갈 수는 없다.
영우는 이 돌다리에서 자기가 방문 가능한 돌들의 개수를 알고 싶어 한다. 방문 가능하다는 것은 현재위치에서 다른 돌을 적절히 밟아 해당하는 위치로 이동이 가능하다는 뜻이다.
현재 위치가 주어졌을 때, 영우가 방문 가능한 돌들의 개수를 출력하시오.
첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000)
다음 줄에는 출발점 s가 주어진다.(1≤s≤n)
[입출력 예]
[풀이]
'방문 가능한 돌' -> DFS로 풀이 진행했습니다.
방문 여부를 체크할 BooleanArray, 돌들의 개수를 담을 cnt 변수를 생성해 줍니다.
val visited = BooleanArray(n) { false }
var cnt = 0
dfs 개념을 활용합니다.
한번 방문한 곳을 탐색하지 않고 왼쪽 오른쪽 상태에 따라 다음 노드로 넘어가면 됩니다.
이미 방문한 곳은 return 하고, 현재 계산 위치에서 주어진 리스트[위치]를 차감하면 left 방향 값을,
현재 계산 위치에서 주어진 리스트[위치]를 더하면 right 방향 값을 얻을 수 있습니다.
if (visited[position]) return
visited[position] = true
cnt++
val left = position - arr[position]
val right = position + arr[position]
그리고 left가 0보다 크면 아직 유효한 인덱스 범위이므로 dfs(left) 호출,
right가 n(리스트 크기) 보다 작은 인덱스 범위면 dfs(right)를 호출하여 방문 위치 체크가 끝날 때까지 재귀 호출합니다.
fun dfs(position: Int) {
if (visited[position]) return
visited[position] = true
cnt++
val left = position - arr[position]
val right = position + arr[position]
if (left >= 0) dfs(left)
if (right < n) dfs(right)
}
이제 해당 함수를 dfs(시작 인덱스)로 호출하기 시작하면 문제 풀이 완료입니다.
아래는 코틀린 전체 코드입니다.
fun main() {
val s = Scanner(System.`in`)
val n = s.nextInt()
s.nextLine()
val arr = s.nextLine().split(" ").map { it.toInt() }
val start = s.nextInt()
val visited = BooleanArray(n) { false }
var cnt = 0
fun dfs(position: Int) {
if (visited[position]) return
visited[position] = true
cnt++
val left = position - arr[position]
val right = position + arr[position]
if (left >= 0) dfs(left)
if (right < n) dfs(right)
}
dfs(start - 1)
println(cnt)
}
