[Algorithm] 백준 숨바꼭질 1697번 - BFS

문제

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

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

입력

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

출력

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

 

---

풀이

• 수빈이가 이동하는 방법은 총 3가지
  • 현재위치+1
  • 현재위치-1
  • 현재위치*2
• 각 위치의 방문여부를 저장하는 배열을 만들고 새로 방문하게 되는 위치에는 직전 위치의 배열값에 +1을 하여 저장한다
• 최종적으로 다음 방문 위치가 동생의 위치일 때 현재 위치의 배열 값이 최종적으로 필요한 이동시간이 된다 (시작이 1이기 때문)

코드

public class BJ1697 {
	static int N;
	static int K;
	static int MAX = 100001;
	static int[] visit = new int[MAX];
	static Queue<Integer> q = new LinkedList<Integer>();
	
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 수빈이 위치
		K = sc.nextInt(); // 동생 위치
		
		System.out.println(bfs(N, K));
	}
	
	static int bfs(int n, int k) {
		q.offer(n); // 수빈이의 위치를 큐에 넣어줌
		visit[n] = 1; // 현재 위치를 방문 표시 
		
		while(!q.isEmpty()) { // 큐에 값이 있는동안 반복 
			int loc = q.poll(); // 큐에서 꺼낸 값이 현재 위치
			
			for(int i=0; i<3; i++) { // 수빈이의 다음 위치를 결정하는 경우는 3가지
				int next; // 수빈이의 다음 위치를 담을 변수
				
				if(i==0) // 현재위치-1 지점으로 이동 
					next = loc-1;
				else if (i==1) //현재위치 +1 지점으로 이동 
					next = loc+1;
				else // 현재위치*2 지점으로 이동
					next = 2*loc;
				
				if(next==k) // 위에서 계산된 다음 위치가 동생이 있는 곳이라면
					return visit[loc]; // 현재 위치를 리턴 (1에서 시작했기 때문)
				
				if(0<=next && next<MAX) { // 다음 위치가 범위 내에 있고 
					if(visit[next] == 0) { // 방문하지 않은 위치라면
						q.offer(next); // 큐에 위치 삽입
						visit[next] = visit[loc]+1; // 다음에 방문할 위치의 값에 이동 횟수 표시
					}
				}
			}
		}
		return 0;
	}
}