[JAVA / 자바] 백준 1697번 - 숨바꼭질

 문제 

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

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

---

 입력 

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

---

 출력 

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

---

---

 문제 접근 방법 

수빈이가 동생을 찾는 최소한의 시간을 출력한다. = 최단 경로 탐색

따라서 너비 우선 탐색 (BFS, Breath First Search) 알고리즘을 이요하여 쉽게 구해줄 수 있다.

 

BFS는 함수에서 선언해줘야 할 자료형으로

1. 큐(다음 경로를 저장)

2. n차원 배열(해당 위치의 경로 길이를 저장)

3. n차원 배열(방문 유무를 판단)

세 가지가 있다.

 

이때, 나는 1, 2번만 사용하여 3번을 선언하지 않고 메모리 사용을 줄일 생각이다.

(∵ 큐에 저장되는 다음 경로는 한 루트를 계속 파는 것이 아니라 해당 위치에서 갈 수 있는 모든 경우를 저장하고 가기 때문에 큐를 deQueue()할 때 나온 다음 경로는 아직 탐색되지 않았던 위치라면 첫 방문이 가장 짧은 시간에 도착한 경우이기 때문이다.)

 

그렇게 BFS로 경로를 탐색하면서 해당 위치까지 가는 최소 시간을 저장을 반복 연산해주다가 다음 경로가 동생이 있는 위치 K가 나오게 되면 경로 탐색을 종료하고 동생이 있는 위치까지 가는 최단 시간을 출력해주면 된다.

 

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

이동하는 방법에 걸리는 시간이 모두 동일하게 1초씩 걸리므로 이전 BFS문제들과 동일하게 풀어주면 돼서 쉽게 풀었던 문제였다.

---

 문제 원본 

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

1697번: 숨바꼭질

 알고리즘 분류 

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색