1697문제 숨바꼭질(DFS/BFS) Java

문제

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

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

입력

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

출력

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

 

출처: <https://www.acmicpc.net/problem/1697>

1697번: 숨바꼭질

 

 

##문제이해##

 

문제가 너무 막연하게 주어져서 당황했다...주어진것들을 정리해보자면 위치 N, 위치K 그리고 이동방법 총 2가지이지만 3가지로 볼수있는 것 +1, -1, *2였다.

보통 그래프의 경우 간선이 주어지는데 간선이 없어서 막막했는데 다른블로그를 보니 경우의수를 계산하더라.. 결국 5 6, 5 4, 5 10, 와 같이 간선이 생긴다. 갈수있는 경로가 생긴다고 보고 수행하면되는거였다.

##고려사항 1번##

처음 제출했을때 방문여부를 체크하는게 없어서 메모리 초과 에러를 발생시켰다.

check[temp-1]==0 등과 같은 부분이 추가된 이유다. 큐는 들어간 순서대로 작동하고 이미 다른숫자가 먼저 들어가서 해당숫자를 0이 아닌 현재값+1로 변경을 했다면 그게 더 빠르다고 보면된다!

선입선출!

##고려사항 2번##

temp-1로 음수값의 범위를 >0처럼 0보다 크게만 잡았었는데 그 부분이 잘못됬었다.. 뺄때는 0과 같아도 되는부분(>=0)으로 변경했더니 틀렸다는게 맞다고 바꼈다 ㅠㅠ 0일경우에는 곱셈이 힘을 못받아서 필요없지 않을까 했는데 그런경우도 빠른방법이 존재하는듯하다.

##내코드##

 

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

public class boj_1967 {
	static int N;
	static int K;
	static int[] check;
	static int cnt=0;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		check = new int[100001];//0부터 100,000까지의 수
		if(N==K) {
			System.out.println(0);
		}else {
			//걷는경우 N-1 or N+1, 순간이동하는경우 N*2위치로 이동. -1 +1 *2를 가지고 탐사하는것.
			bfs(N);
			System.out.println(check[K]);
		}
		
	}
	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(N);
		check[N]=0; //초기시작값은 0
		
		while(!q.isEmpty()) {
			int temp = q.poll();
			//종료조건
			if (check[K] != 0) break;
			
			//간선 1번방법
			if(temp+1<check.length && check[temp+1]==0) {
				check[temp+1]=check[temp]+1;
				q.offer(temp+1);
			}
			//간선 2번방법
			if(temp-1<check.length && temp-1>=0 &&check[temp-1]==0) {
				check[temp-1]=check[temp]+1;
				q.offer(temp-1);
			}
			//간선 3번방법 방문을 안한상태라면 0의 숫자가 들어가있다(check[temp*2]==0)
			if(temp*2 <check.length && check[temp*2]==0) {
				check[temp*2]=check[temp]+1;
				q.offer(temp*2);
			}
			
		}
		
	}

}