[백준] 1326 폴짝폴짝 - 너비우선탐색(BFS) JAVA

https://www.acmicpc.net/problem/1326

코드설명

너비우선탐색(BFS)을 활용합니다.

 

이 문제에서 어려운점은, 어떤 알고리즘을 사용해야하는 것인가?입니다.

1. 최적 부분구조

2. DFS

3. BFS

 

이 3가지가 떠올랐습니다.

 

먼저 이 문제에서 DFS와 최적 부분구조가 안되는 이유는 점프가 뒤로도, 앞으로도 가능하다는 점입니다.

만약 점프가 앞으로만 가능했다면 최적 부분구조가 성립하므로 DFS를 활용해서 시간 안에 해결할 수 있겠지요.

하지만, 뒤로도 가능하기에 무한한 방식의 점프 방식이 나올 수 있습니다. 또 사이클도 피해야하고요.

 

구현하며 겪었던 생각은 아래코드와 함께 작성했습니다.

코드

정답코드1입니다.

BFS를 활용한 코드입니다.

BFS를 활용하여 한번에 여러 Queue들을 탐색하므로 중복연산을 피할 수 있고, 최적의 점프로 찾을 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R;
	static int answer = 0;
	static int[] arr;
	static int[] cache = new int[5];
	static boolean[] visited = new boolean[10001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken()) - 1;
		int b = Integer.parseInt(st.nextToken()) - 1;
		
		Arrays.fill(cache, -1);
//		answer = DFS(a, b, new boolean[N]);
		answer = BFS(a, b);
		if(answer >= 10001) System.out.println(-1);
		else System.out.println(answer);
	}
	
	
	static int BFS(int src, int target) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {src, 0});
		boolean[] visited = new boolean[N];
		visited[src] = true;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int now = temp[0];
			int moved = temp[1];
			
			if(now == target) {
				return moved;
			}
			
			for(int next = now + arr[now] ; next < N; next+=arr[now]) {
				if(visited[next] == false) {
					q.offer(new int[] {next, moved + 1});
					visited[next] = true;
				}
			}
			
			for(int next = now - arr[now] ; next >= 0; next -= arr[now]) {
				if(visited[next] == false) {
					q.offer(new int[] {next, moved + 1});
					visited[next] = true;
				}
			}
			
		}
		
		return -1;
	}
	
}

 

DFS 및 브루트포스를 활용합니다.

3번코드처럼 최적 부분구조가 안됨을 꺠닫고, DFS로 사이클이 발생하지 않도록 유의하며 작성했습니다.

하지만, 시간초과가 발생합니다.

이유가 무엇일까요? 이유는 visited[now] = false 로 원상복구를 해주면서 이전에 탐색햇던 부분도 다시 탐색하는 것 입니다.

이를 해결하려면, visited[now] = true로 바꾸고, visited[now] = false 로 원상복구를 하지 않고, 이전에 탐색햇던 부분을 다시 탐색하지않도록 해야합니다. 하지만, 이렇게 할경우 좀 더 빠르게 도착하는 경우, 즉 최소의 경우를 탐색하지 못합니다.

이 문제의 경우 DFS를 사용하는 것보다는 BFS를 사용해야 함을 알 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R;
	static int answer = 0;
	static int[] arr;
	static int[] cache = new int[5];
	static boolean[] visited = new boolean[10001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken()) - 1;
		int b = Integer.parseInt(st.nextToken()) - 1;
		
		Arrays.fill(cache, -1);
		answer = DFS(a, b, new boolean[N]);
		if(answer >= 10001) System.out.println(-1);
		else System.out.println(answer);
	}
	
	static int DFS(int now, int target, boolean[] visited) {
		if(now == target) {
			return 0;
		}
		
		visited[now] = true;
		int ret = 10001;
		for(int next = now + arr[now] ; next < N && next >= 0; next+=arr[now]) {
			if(visited[next] == false)
				ret = Math.min(ret, DFS(next, target, visited) + 1);
		}
		
		for(int next = now - arr[now] ; next < N && next >= 0; next-=arr[now]) {
			if(visited[next] == false)
				ret = Math.min(ret, DFS(next, target, visited) + 1);
		}
		visited[now] = false;
		return ret;
	}
	
}

 

3번 코드입니다. 처음에 재귀와 메모이제이션을 활용하려한 코드입니다.

하지만, 이 문제에서는 최적부분구조가 작동하지 않습니다.  왜일까요? 이유는 "순서가 강제되지 않기 때문입니다."

점프가 앞으로도 가능하고 뒤로도 가능하기 떄문입니다. 만약 LIS 문제처럼 한 방향으로만, 즉 증가하는 부분으로만 이동한다면 최적 부분구조가 성립하지만, 이 문제에서는 최적 부분구조가 성립하지 않음을 알 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R;
	static int answer = 0;
	static int[] arr;
	static int[] cache = new int[10001];
	static boolean[] visited = new boolean[10001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken()) - 1;
		int b = Integer.parseInt(st.nextToken()) - 1;
		
		Arrays.fill(cache, -1);
		answer = DFS(a, b);
		if(answer >= 10001) System.out.println(-1);
		else System.out.println(answer);
	}

	
	static int DFS(int now, int target) {
		if(now == target) {
			return 0;
		}
		if(cache[now] != -1) return cache[now];
		
		int ret = 10001;
		for(int next = now + arr[now] ; next < N && next >= 0; next+=arr[now]) {
			if(visited[next] == false)
				ret = Math.min(ret, DFS(next, target, visited) + 1);
		}
		for(int next = now - arr[now] ; next < N && next >= 0; next-=arr[now]) {
			if(visited[next] == false)
				ret = Math.min(ret, DFS(next, target, visited) + 1);
		}
		return cache[now] = ret;
	}
	
}