문제 내용은 입력으로 돌다리를 받은 뒤, 마지막 입력받은 값 위치에서 시작해서, 밟고 있는 인덱스의 숫자만큼 좌우로 이동했을 경우, 최대 몇 칸을 밟을 수 있냐는 것인데
입력을 보면 무조건 한 칸은 밟을 수 있고, 이후부터 좌우로 움직여서 최대 갯수를 계산해야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static boolean[] visited;
static int[] map;
static int cnt = 1;
public static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
int poll = queue.poll();
visited[poll] = true;
if (poll + map[poll] < map.length) {
if (!visited[poll + map[poll]]) {
queue.add(poll + map[poll]);
visited[poll + map[poll]] = true;
cnt++;
}
}
if (poll - map[poll] > -1) {
if (!visited[poll - map[poll]]) {
queue.add(poll - map[poll]);
visited[poll - map[poll]] = true;
cnt++;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
map = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
visited = new boolean[count];
bfs(Integer.parseInt(br.readLine()) - 1);
System.out.println(cnt);
}
}
문제는 입력값의 범위가 매우 크기 때문에 BFS를 사용해서 해결해야 하는데, Queue를 사용한 뒤 시작 위치에서 좌우로 이동할 수 있는지 확인하고, 이동 가능하다면 Queue에 추가해주면서 횟수를 더해준 후 BFS가 끝나고 나면 횟수를 출력해주면 끝이 난다.
Leave a Reply