영우는 지금 n개의 돌이 일렬로 놓여있는 돌다리에 있다. 그리고 돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있는데, 이때 돌다리 밖으로 나갈 수는 없다.
영우는 이 돌다리에서 자기가 방문 가능한 돌들의 개수를 알고 싶어한다. 방문 가능하다는 것은 현재위치에서 다른 돌을 적절히 밟아 해당하는 위치로 이동이 가능하다는 뜻이다.
현재 위치가 주어졌을 때, 영우가 방문 가능한 돌들의 개수를 출력하시오.
입력
첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000)
다음 줄에는 출발점 s가 주어진다.(1≤s≤n)
출력
영우가 방문 가능한 돌들의 개수를 출력하시오.
풀이 코드 - DFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int cnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] stones = new int[n];
String[] strings = br.readLine().split(" ");
for (int i = 0; i < n; i++) stones[i] = Integer.parseInt(strings[i]);
int s = Integer.parseInt(br.readLine());
dfs(stones, s - 1);
System.out.println(cnt);
}
private static void dfs(int[] stones, int idx) {
if (stones[idx] == 0) return;
int left = idx - stones[idx];
int right = idx + stones[idx];
stones[idx] = 0;
cnt++;
if (left >= 0) dfs(stones, left);
if (right <= stones.length - 1) dfs(stones, right);
}
}
Time: 240 ms
Memory: 26236 KB
문제를 보고 일단 DFS 가 먼저 생각나서 DFS 로 풀었다. 시작 인덱스 s - 1 에서 이동할 수 있는 왼쪽과 오른쪽 인덱스를 구하고 한번 접근한 인덱스는 0 을 할당해서 방문 유무를 체크했다.
왼쪽 인덱스 값은 0 보다 크거나 같을 때만 접근할 수 있고 오른쪽 인덱스는 돌다리 배열의 크기보다 작아야 한다. 쓰고보니 n 보다 작은 경우로 조건식을 수정하면 더 깔끔할 것 같다.
그리고 이미 방문한 인덱스인 경우엔 더 진행하지 않는다. 난이도는 쉬운 문제였지만 BFS 로는 감이 오질 않아 다른 사람의 풀이를 참고했으며 아래와 같다.
다른 사람의 풀이 - BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] stones = new int[n];
String[] strings = br.readLine().split(" ");
for (int i = 0; i < n; i++) stones[i] = Integer.parseInt(strings[i]);
int s = Integer.parseInt(br.readLine());
boolean[] visited = new boolean[n];
int[] bias = {1, -1};
int cnt = 1;
Deque<Integer> deque = new ArrayDeque<>();
deque.push(s - 1);
visited[s - 1] = true;
while (!deque.isEmpty()) {
int q = deque.pop();
for (int b : bias) {
int abs = q + stones[q] * b;
if (0 <= abs && abs < n && !visited[abs]) {
visited[abs] = true;
cnt++;
deque.push(abs);
}
}
}
System.out.println(cnt);
}
}
Time: 232 ms
Memory: 26336 KB
DFS 에 비해 속도가 조금 더 빠르다. BFS 구조는 툭 치면 바로 나올 정도여야 한다는데 아직 많이 부족하다. 풀이 개념은 DFS 방식과 비슷하다.
해당 풀이에서 참신한건 bias 배열로 해당 배열을 통해 양수와 음수 값을 구한다는 점이었다. 그리고 삽입 속도에서 LinkedList 보다 더 빠른 ArrayDeque 를 구현한 Deque 클래스를 사용했다.
