백준 1697 숨바꼭질(자바)

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

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

BFS 문제이다.

주어진 N에서 시작해서 3가지 경우를 보고 가장 먼저 도착하는 횟수를 출력하면 된다.

 

우선 전체 코드를 보자.

package 단계별문제;                                                                               
                                                                                             
import java.util.Arrays;                                                                     
import java.util.LinkedList;                                                                 
import java.util.Queue;                                                                      
import java.util.Scanner;                                                                    
                                                                                             
public class baek_숨바꼭질_1697_실버1 {                                                            
	static int N; // 수빈이 위치                                                                  
	static int K; // 동생 위치                                                                   
	static boolean[] visited; // 방문쳌                                                         
	static int[] result;                                                                     
                                                                                             
	public static void main(String[] args) {                                                 
		Scanner sc = new Scanner(System.in);                                                 
		N = sc.nextInt();                                                                    
		K = sc.nextInt();                                                                    
		visited = new boolean[100001]; // 최대 10만까지니                                          
		result = new int[100001];                                                            
                                                                                             
		BFS(N);                                                                              
		System.out.println(result[K]);                                                       
	}                                                                                        
                                                                                             
	public static void BFS(int N) {                                                          
		Queue<Integer> q = new LinkedList<Integer>();                                        
		q.add(N);                                                                            
		visited[N] = true;                                                                   
		result[N] = 0; // 결과배열에 우선 0 넣어줌                                                     
		while (!q.isEmpty()) {                                                               
			int curr = q.poll();                                                             
			if (curr == K) { // 이동해서 K에 도착하면 리턴                                              
				return;                                                                      
			}                                                                                
			for (int i = 0; i < 3; i++) { // 3가지 경우를 보니깐                                     
				if (i == 0) {                                                                
					// 현재 위치에서 1을 빼도 범위에 있고 false면                                           
					if (curr - 1 >= 0 && !visited[curr - 1]) {                               
						visited[curr - 1] = true; // 체크하고                                    
						q.add(curr - 1); // 넣고                                               
						result[curr - 1] = result[curr] + 1; // 이전좌표에서 +1해줌                  
					}                                                                        
                                                                                             
				} else if (i == 1) {                                                         
					// 현재 위치에서 1을 더해도 범위에 있고 false면                                          
					if (curr + 1 < 100001 && !visited[curr + 1]) {                           
						visited[curr + 1] = true; // 체크하고                                    
						q.add(curr + 1); // 넣고                                               
						result[curr + 1] = result[curr] + 1; // 이전좌표에서 +1해줌                  
					}                                                                        
				} else if(i==2) {                                                            
					// 현재 위치에서 2를 곱해도 범위에 있고 false면                                          
					if (curr * 2 < 100001 && !visited[curr * 2]) {                           
						visited[curr * 2] = true; // 체크하고                                    
						q.add(curr * 2); // 넣고                                               
						result[curr * 2] = result[curr] + 1; // 이전좌표에서 +1해줌                  
					}                                                                        
				}                                                                            
			}                                                                                
                                                                                             
		}                                                                                    
	}                                                                                        
}

 

이제 하나씩 살펴보자.

 

static int N; // 수빈이 위치            
static int K; // 동생 위치             
static boolean[] visited; // 방문쳌   
static int[] result; // 이동 횟수 기록

네 가지 변수를 스태틱으로 선언했다.

 

public static void main(String[] args) {                     
	Scanner sc = new Scanner(System.in);                     
	N = sc.nextInt();                                        
	K = sc.nextInt();                                        
	visited = new boolean[100001]; // 최대 10만까지니              
	result = new int[100001];                                
                                                             
	BFS(N);                                                  
	System.out.println(result[K]);                           
}

입력을 받고 문제 조건에서 수빈이랑 동생은 10만 이하까지 존재하니 100001의 배열을 선언했다.

result배열은 이동 횟수를 기록하기 위해 선언했다.

 

public static void BFS(int N) {                                   
	Queue<Integer> q = new LinkedList<Integer>();                 
	q.add(N);                                                     
	visited[N] = true;                                            
	result[N] = 0; // 결과배열에 우선 0 넣어줌                              
	while (!q.isEmpty()) {                                        
		int curr = q.poll();                                      
		if (curr == K) { // 이동해서 K에 도착하면 리턴                       
			return;                                               
		}

BFS를 돌린다.

큐를 생성하고 큐에 현재 언니의 위치인 N을 넣고 방문했다고 체크를 한다.

그리고 결과 배열에는 0을 넣어준다. (이제 이동할때마다 1씩 증가)

리턴 조건으로 큐에서 꺼낸 값이 동생의 위치면 리턴한다.

 

for (int i = 0; i < 3; i++) { // 3가지 경우를 보니깐                              
	if (i == 0) {                                                         
		// 현재 위치에서 1을 빼도 범위에 있고 false면                                    
		if (curr - 1 >= 0 && !visited[curr - 1]) {                        
			visited[curr - 1] = true; // 체크하고                             
			q.add(curr - 1); // 넣고                                        
			result[curr - 1] = result[curr] + 1; // 이전좌표에서 +1해줌           
		}                                                                 
                                                                          
	} else if (i == 1) {                                                  
		// 현재 위치에서 1을 더해도 범위에 있고 false면                                   
		if (curr + 1 < 100001 && !visited[curr + 1]) {                    
			visited[curr + 1] = true; // 체크하고                             
			q.add(curr + 1); // 넣고                                        
			result[curr + 1] = result[curr] + 1; // 이전좌표에서 +1해줌           
		}                                                                 
	} else if(i==2) {                                                     
		// 현재 위치에서 2를 곱해도 범위에 있고 false면                                   
		if (curr * 2 < 100001 && !visited[curr * 2]) {                    
			visited[curr * 2] = true; // 체크하고                             
			q.add(curr * 2); // 넣고                                        
			result[curr * 2] = result[curr] + 1; // 이전좌표에서 +1해줌           
		}                                                                 
	}

총 3가지 경우로 나누었다.

1. 현재 위치에서 -1로 가는 경우

우선 범위 내에 있는지 확인하고 false인지 확인한다.

둘 다 맞다면 방문체크 표시를 하고 큐에 집어넣은뒤 기존 curr위치에서 +1을 해서 더해준다.

 

2. 현재 위치에서 +1로 가는 경우

우선 범위 내에 있는지 확인하고 false인지 확인한다.

둘 다 맞다면 방문체크 표시를 하고 큐에 집어넣은뒤 기존 curr위치에서 +1을 해서 더해준다.

 

3. 현재 위치에서 순간이동(x2) 하는 경우

우선 범위 내에 있는지 확인하고 false인지 확인한다.

둘 다 맞다면 방문체크 표시를 하고 큐에 집어넣은뒤 기존 curr위치에서 +1을 해서 더해준다.

 

result가 어떻게 변하는지 확인해보자.

사진처럼 처음에 N=5인 위치는 0으로 설정하고 이제 이동할때마다 그 이전 위치에서 +1씩 늘어나게 된다.

17이 동생의 위치고 정답을 출력하면 4가 정상적으로 뽑아져 나온다.