분류
너비 우선 탐색, 그래프 이론, 그래프 탐색
문제 설명
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력
5 17
예제 출력
4
코드 - 숨바꼭질.java
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
private static int MAX = 100001;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 수빈이의 위치
int K = sc.nextInt(); // 동생의 위치
int[] check = new int[MAX]; // 각 위치에 도달하기까지 걸린 시간을 저장하는 배열
Arrays.fill(check, -1); // 초기에는 모든 위치를 도달하지 않은 상태(-1)로 세팅
Queue<Integer> queue = new LinkedList<>();
queue.add(N);
check[N] = 0;
while (!queue.isEmpty()) {
int current = queue.poll();
if (current == K) {
System.out.println(check[current]);
break;
}
int[] nextStates = {current - 1, current + 1, 2 * current}; // 이동 가능한 상태들
for (int nextState : nextStates) {
// 다음 상태가 범위 내에 있고 아직 방문하지 않은 상태라면
if (nextState >= 0 && nextState < MAX && check[nextState] == -1) {
queue.add(nextState);
check[nextState] = check[current] + 1; // 현재까지의 시간에 1초 추가
}
}
}
}
}
코드 분석하기
1. private static int MAX = 100001;: 최대 위치 값을 상수로 선언합니다. 0부터 100,000까지의 위치를 고려해야 하므로, 배열 인덱스로 사용하기 위해 1을 더한 값인 100,001을 선언합니다.
2. public static void main(String[] args): Java 프로그램의 시작점인 main 함수를 선언합니다.
3. Scanner sc = new Scanner(System.in);: 표준 입력으로부터 데이터를 읽기 위한 Scanner 객체를 생성합니다.
4. int N = sc.nextInt(); int K = sc.nextInt();: 수빈이의 위치 N과 동생의 위치 K를 입력받습니다.
5. int[] check = new int[MAX];: 각 위치에 도달하는 데 걸린 시간을 저장하는 배열을 선언합니다. 배열의 크기는 MAX로 설정하여 모든 가능한 위치를 커버합니다.
6. Arrays.fill(check, -1);: 배열의 모든 요소를 -1로 초기화합니다. -1은 아직 해당 위치에 도달하지 않았음을 의미합니다.
7. Queue<Integer> queue = new LinkedList<>();: BFS를 수행하기 위한 Queue를 선언하고, LinkedList로 초기화합니다.
8. queue.add(N); check[N] = 0;: BFS를 시작하기 위해, 수빈이의 초기 위치를 큐에 넣고, 해당 위치에 도달하는 데 걸리는 시간을 0으로 설정합니다.
9. while (!queue.isEmpty()): 큐가 비어있지 않은 동안 BFS를 수행합니다.
10. int current = queue.poll();: 큐의 맨 앞에 있는 요소를 꺼내고, 현재 위치로 설정합니다.
11. if (current == K): 현재 위치가 동생의 위치와 같다면, 동생을 찾은 것이므로 해당 위치에 도달하는 데 걸린 시간을 출력하고 프로그램을 종료합니다.
12. int[] nextStates = {current - 1, current + 1, 2 * current};: 현재 위치에서 이동할 수 있는 세 가지 위치를 배열로 만듭니다.
13. for (int nextState : nextStates): 세 가지 위치를 순회합니다.
14. if (nextState >= 0 && nextState < MAX && check[nextState] == -1): 만약 이동하려는 위치가 0 이상, MAX 미만이고, 아직 도달하지 않은 위치라면 (즉, check[nextState]가 -1이라면), 해당 위치를 큐에 넣고, 해당 위치에 도달하는 데 걸린 시간을 현재까지의 시간에 1초를 더한 값으로 설정합니다. 이동하려는 위치가 범위 밖이거나 이미 방문한 위치라면 해당 위치는 무시됩니다.
15. BFS 과정이 끝나면, 동생의 위치에 도달하는 최단 시간이 출력됩니다. 동생의 위치에 도달하지 못하는 경우는 없습니다.
백준에서 문제 풀어보기
