[백준] S2 14248번 점프 점프 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

14248번: 점프 점프

[문제] 

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

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

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

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

[입력]

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

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

[출력]

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

 

---

[풀이]

1. 값들을 입력받아준다.

2. 시작점을 기준으로 BFS 탐색을 한다.

3. BFS 함수에 들어가면 현재 위치를 Queue에 담아주고, 방문처리와 방문한 돌의 수를 증가시켜준다.

4. 좌우로만 이동하면 되므로 2방향만 탐색하고 현재 위치에 현재 위치의 값 * dr 배열의 값을 더해 탐색을 해준다.

5. 이미 방문했거나 범위를 벗어나는 경우는 넘어가고 아니라면 방문한 돌의 수를 증가시키고 추가 탐색을 해준다.

6. 모든 탐색이 끝나고 나면 결과를 출력해준다.

[접근]

1. 2차원 배열이 아닌 1차원 배열에서 BFS 탐색을 하며, 이미 방문하지 않은 곳의 경우에만 카운트를 증가시켜 출력해주면 되겠다고 생각하였다.

[코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n, s, cnt;
	static int[] map;
	static boolean[] visited;
	
	// 왼쪽과 오른쪽으로만 탐색
	static int[] dr = {-1, 1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		map = new int[n];
		visited = new boolean[n];
		
		// 값 입력 받기
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}
		
		// 입력받기 -> 배열에서 처리할꺼니까 -1해줌
		s = Integer.parseInt(br.readLine()) - 1;
		
		bfs(s);
		
		System.out.println(cnt);
	}
	
	public static void bfs(int x) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(x);

		// 시작지점 방문
		visited[x] = true; 
		cnt = 1;
		
		while (!q.isEmpty()) {
			int pos = q.poll();
			
			for (int i = 0; i < 2; i++) {
				// 현재 위치 + 현재 위치의 돌에 적힌 값 (좌우로 이동하기 위해 dr의 값을 곱해줌)
				int nx = pos + (map[pos] * dr[i]);
				
				// 돌다리 벗어나는 경우
				if (nx < 0 || nx >= n)
					continue;
				// 이미 방문한 경우
				if (visited[nx])
					continue;
				
				q.add(nx);
				visited[nx] = true; // 방문처리
				cnt++; // 방문한 돌다리 횟수 증가
			}
		}
	}
}