[백준] 1697 숨바꼭질 - BFS(너비우선탐색) JAVA

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

코드설명

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

 

처음에 제출하고서 시간초과 및 메모리초과가 나길래 원인이 뭐지하고 각 시간복잡도, 공간복잡도를 분석하다가

if(visited[next] == true) continue;

위의 코드처럼 이미 방문한 곳을 다시는 방문하지 않도록 처리하는 코드를 잊었다는 것을 알았습니다.

해당 사항만 수정해주면 BFS로 시간안에 처리가능합니다.

코드

정답코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	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());
		K = Integer.parseInt(st.nextToken());
		
		System.out.println(BFS(N, K));
	}
	
	static int BFS(int src, int target) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {src, 0});
		boolean[] visited = new boolean[100001];
		visited[src] = true;
		int ret = 0;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			if(temp[0] == target) {
				return temp[1];
			}
			
			for(int dir : new int[] {-1, 1} ) {
				int next = temp[0] + dir;
				int nCnt = temp[1] + 1;
				if(next < 0 || next > 100000) continue;
				if(visited[next] == true) continue;
				q.offer(new int[] {next, nCnt});
				visited[next] = true;
			}
			int next = temp[0] * 2;
			int nCnt = temp[1] + 1;
			if(next < 0 || next > 100000) continue;
			if(visited[next] == true) continue;
			q.offer(new int[] {next, nCnt});
			visited[next] = true;
		}
		return -1;
	}
}

 

 

시간초과 및 메모리초과 나는 코드입니다.

우선 시간복잡도와 메모리복잡도를 계산합니다.

시간복잡도의 경우 O(K) 입니다. 이유는 visited 배열을 활용하여 한번씩만 공간을 방문하기 때문입니다. O(100,000)이면 일반적으로 1억에 1초가 걸리는 컴퓨터 시스템에서 1ms 만에 해결해야하는 문제입니다만, 시간초과가 납니다. 제가 잘못계산했다는 것이겠지요.

공간복잡도의 경우 visited[i] = new boolean[100,000]에서 10^5 * 1byte 로 약 100 KB입니다.  메모리가 초과나지 않을 것이라 생각했는데, 초과나는 이유는 BFS에 너무 많은 데이터가 쌓여서 그러는 것 같습니다. 

시간초과를 해결하려면 어떻게 해야할까요.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	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());
		K = Integer.parseInt(st.nextToken());
		
		System.out.println(BFS(N, K));
	}
	
	static int BFS(int src, int target) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {src, 0});
		boolean[] visited = new boolean[100001];
		visited[src] = true;
		int ret = 0;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			if(temp[0] == target) {
				return temp[1];
			}
			for(int dir : new int[] {-1, 1} ) {
				int next = temp[0] + dir;
				int nCnt = temp[1] + 1;
				if(next < 0 || next > 100000) continue;
				q.offer(new int[] {next, nCnt});
				visited[next] = true;
			}
			int next = temp[0] * 2;
			int nCnt = temp[1] + 1;
			if(next < 0 || next > 100000) continue;
			q.offer(new int[] {next, nCnt});
			visited[next] = true;
		}
		return -1;
	}
}