[백준 1697] 숨바꼭질 - 자바

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

1697번: 숨바꼭질

---

1. 풀이

처음엔 헤맸지만, 풀고나니 BFS에 대해서 더 깊은 이해를 하게 되는 좋은 문제인 듯 싶다.

 

수빈이는 +1 , -1 , *2로 움직일 수 있다. 그리고 동생은 움직이지 않는다. 

 

그러므로 수빈이의 위치값에서 BFS를 진행한다. 조건은 아래와 같다.

 

1. 수빈이가 움직이는 위치가 범위(0-100000)를 벗어나진 않는지 확인한다.

 

2. 이전에 방문했던 곳인지 아닌지 확인한다. BFS로 인해 선입선출을 하므로, 먼저 해당 위치에 도착한 depth가 해당 위치를 차지하므로, 이미 차지한 위치는 다시 방문할 필요가 없다.

 

위 조건이 충족되는 모든 위치로 이동한다. 그리고 도착할 때까지 반복을 한다.

 

visited는 방문체크도 하고, 해당 위치에 도착한 시간을 저장하게 된다. ( 이 문제에서 BFS에서의 depth를 시간으로 봐도 무방하다. )

 

2. 코드

---

import java.util.*;

public class Main {
	
	static int MAX = 100001;
	
	static void bfs(int N, int K, int[] visited) {
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.offer(N);
		visited[N] = 1; // 방문 체크
		
		int tmp;
		while(!queue.isEmpty()) {
			tmp = queue.poll();
			// 탈출 조건
			if(tmp == K)
				break;
			
			// +1
			if(tmp+1 < MAX && visited[tmp+1] == 0) {
				queue.offer(tmp+1);
				visited[tmp+1] = visited[tmp]+1;
				System.out.println(tmp+1);
			}
			
			// -1
			if(tmp-1 >= 0 && visited[tmp-1] == 0) {
				queue.add(tmp-1);
				visited[tmp-1] = visited[tmp]+1;
				System.out.println(tmp-1);
			}
			
			// *2
			if(2*tmp < MAX && visited[tmp*2] == 0) {
				queue.add(2*tmp);
				visited[tmp*2] = visited[tmp]+1;
				System.out.println(2*tmp);
			}
			
		}
		
		System.out.println(visited[K]-1);
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] visited = new int[MAX]; // 방문 체크겸 방문한 시간 저장.
		
		bfs(N, K, visited);
		
		sc.close();
		return;
	}
}