[JAVA] 백준 알고리즘 1697번 문제풀이 (숨바꼭질)

 

 

 

 

 

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

1697번: 숨바꼭질

 

 

 

● 숨바꼭질 (1697번) - BFS

 

 

 

 

 

 

package quiz;

import java.util.*;

public class Quiz_1697 {

	public static final int MAX = 1000000;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		boolean[] check = new boolean[MAX];
		int[] dist = new int[MAX];
		check[n] = true;
		dist[n] = 0;
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(n);
		while (!q.isEmpty()) {
			int now = q.remove();
			if (now - 1 >= 0) {
				if (check[now - 1] == false) {
					q.add(now - 1);
					check[now - 1] = true;
					dist[now - 1] = dist[now] + 1;
				}
			}
			if (now + 1 < MAX) {
				if (check[now + 1] == false) {
					q.add(now + 1);
					check[now + 1] = true;
					dist[now + 1] = dist[now] + 1;
				}
			}
			if (now * 2 < MAX) {
				if (check[now * 2] == false) {
					q.add(now * 2);
					check[now * 2] = true;
					dist[now * 2] = dist[now] + 1;
				}
			}
		}
		System.out.println(dist[m]);
	}
}

* 소스풀이

​

수빈이가 있는 위치 n과 동생이 있는 위치 m을 입력받습니다.

check배열을 통해 다음칸에 이동했는지의 여부를 확인하기위해 선언하고, dist배열 선언해줍니다.

수빈이의 위치는 방문했기에 true로 바꿔주고, 시간은 0으로 셋팅해줍니다.

큐를 생성해주고, n의 값을 넣어 add해줍니다.

while 반복문을 통해 큐를 참고하고 있는 a인스턴스가 비어있지않다면, q를 지워주고 now변수에 넣어줍니다.

우선, 수빈이의 위치가 now이므로, now가 1초후에 -1 , +1 , 순간이동은 *2라고 했습니다.

그래서 3개 모두 if문을 통해 만들어주고, -1은 0보다 클경우, check배열에 방문하지않았다면(false라면)

add해주고, 방문을 true로 변경해줍니다. 그리고 현재 now에서 +1을 해줘서 저장해줍니다.

+1과 *2도 이와동일하게 하되, 이 두개는 final인 MAX보다 크면 빠져나오게 했습니다.

이처럼 +1로 계속 추적하면서 누적해주다보면 m의 값에 누적된 값 (최단시간) 이 출력됩니다.

 

 

< 백준알고리즘 강의를 보고 참고하였습니다! >

 

---