1697 - 숨바꼭질 (BFS)

---

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

//백준
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int subin = sc.nextInt();
		int dong = sc.nextInt();

		int[] visited = new int[2000001];

		Queue<Integer> q = new LinkedList<Integer>();

		// 시작노드
		q.offer(subin);
	

		int a = 0;


		while (!q.isEmpty()) {

			a = q.poll();
			
			if (a == dong) {
				System.out.println(visited[a]);
				break;
			}
			
			if (a<100001) {
			if (visited[a + 1] == 0) {
				q.offer(a + 1);
				visited[a + 1] = visited[a] + 1;

			}
			if(a>0) {
				if (visited[a - 1] == 0) {
					q.offer(a - 1);
					visited[a - 1] = visited[a] + 1;
				}
			}

			
				if (visited[2 * a] == 0) {
					q.offer(2 * a);
					visited[2 * a] = visited[a] + 1;
				}
			}



		}

	}

}

 

탐색여부를 true / false 로 주지 않았다.

그 이유는 몇번만에 탐색했는지 출력해야하는데, 기존에 탐색되었던곳에 1부터 시작해서 +1 시켰다.

 

if문 0보다크거나 100001보다 작게 둔 이유는 -1 시킬때 0보다 커야하고, x2가 있다보니 10만이상의 값은 의미가 없기 때문에 따로 큐에 담을 필요가 없었다.