[백준 1697] 숨바꼭질 in JAVA

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

※ 풀이 방법

 (원래는 블로그에 안 올리려고 했는데 메모리 초과랑 index 런타임 에러가 너무 많이나서 기록을 위해 포스팅하게 되었다.

기본적인 아이디어는 BFS를 사용하였다. 큐에 수빈이의 현재 위치와 지난 시간을 저장하였다.

수빈이가 동생을 찾을 때까지 반복문을 수행하였다.

먼저 수빈이의 현재 위치를 꺼내고 그 위치가 동생의 위치와 같을 경우 답을 출력해주었다.

 

다음은 오류 정리이다.

 

 • 메모리 초과

 이미 방문한 위치 체크를 안 해줘서 생겼던 문제이다. 그래프 탐색 문제에서 가장 기본적인 부분인데 이를 간과했다.

  -> boolean 배열을 통해 방문한 위치 체크해줬다.

 • 런타임 에러(ArrayindexOutOfBounds)

 index가 음수일 경우를 체크해주지 않아서 생긴 문제이다. 배열에서는 음수 index를 쓸 수 없다.... (바보)

  -> 반복문 안에 조건문을 추가해주었다.

※ 문제 풀이 코드

import java.util.LinkedList;
import java.util.Scanner;

public class BOJ_1697 {
	public static LinkedList<int []> queue=new LinkedList<int []>();
	public static int [] temp1;
	public static int [] temp2;
	public static int [] temp3;
	public static int [] a;
	public static boolean [] ck;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input=new Scanner(System.in);
	
		int N=input.nextInt();
		int K=input.nextInt();
		
		a = new int[2];
		a[0] = N;
		a[1] = 0;
		
		queue.addLast(a);
		
		int ans=0;
		ck=new boolean[2000000];//메모리 초과 해결
		
		while(true) {
			a=queue.removeFirst();
			if(a[0]==K) break; //답일 경우
			if(a[0]>100010||a[0]<0) continue; //index 런타임에러 해결
			if(ck[a[0]]) continue;
			ck[a[0]]=true;
			temp1=new int[2];
			temp2=new int[2];
			temp3=new int[2];
			
			temp1[0]=a[0]-1;//한 칸 뒤로
			temp2[0]=a[0]+1;//한 칸 앞으로
			temp3[0]=a[0]*2;//순간이동
			temp1[1]=a[1]+1;
			temp2[1]=temp1[1];
			temp3[1]=temp1[1];
			
			queue.addLast(temp1);
			queue.addLast(temp2);
			queue.addLast(temp3);
		}
		
		System.out.println(a[1]);
	}

}