문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
풀이
시간복잡도 면에서 주어진 수는 10만이다. 따라서 이중for문을 쓰면 안되고
O(nlogn)으로 풀수있는 방법을 생각해야한다.
수빈이가 이동할수있는곳을 방문체크하듯이 진행하면 각 칸마다의 최소 이동시간을 알 수 있게된다.
따라서 너비우선탐색(BFS)를 사용했다.
과정은 다음과 같다. 수빈 위치가 5, 동생이 17에 있다고 가정하고 그림을 보면 될것같다.
이런 과정을 통해 수진의 위치 5에서 동생의 위치 17까지 도달하는 빠른시간은 4 이다.
그림이 이해가 안가거나 BFS문제가 어렵게 느껴진다면 아래 링크글에 있는 문제와 그림(큐 그림 위주로)
을 봐주면 될것같다.
https://developerjisu.tistory.com/3
예제 입력 예시
5 17
예제 출력
4
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
//1697번
public class Main {
static boolean[] visited; //방문체크
static int[] map; //숨바꼭질 맵
static int K; //동생의 위치
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
map = new int[100001];
visited = new boolean[100001];
int N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
//동생이 수빈이보다 오른쪽에 있는 경우
if(N<K){
bfs(N);
System.out.println(map[K]);
}
//동생이 수빈이보다 왼쪽에 있는 경우
else System.out.println(N-K);
}
static void bfs(int n){
Queue<Integer>queue = new LinkedList<>();
queue.add(n);
map[n] = 0;
visited[n] = true;
while(!queue.isEmpty()){
int start = queue.poll();
if(start>0&&!visited[start-1]){
queue.add(start-1);
visited[start-1] = true;
map[start-1] = map[start]+1;
}
if(start<100000&&!visited[start+1]){
queue.add(start+1);
visited[start+1] = true;
map[start+1] = map[start]+1;
}
if(start<50001&&!visited[start*2]){
queue.add(start*2);
visited[start*2] = true;
map[start*2] = map[start]+1;
}
}
}
}
문제 출처
https://www.acmicpc.net/problem/1697
'알고리즘 > 자바' 카테고리의 다른 글
[백준 알고리즘] 15650번 자바(Java) N과 M(2) (0) | 2023.08.01 |
---|---|
[백준 알고리즘] 1967번 자바(Java) 트리의 지름 (0) | 2023.07.26 |
[백준 알고리즘] 2504번 자바(Java) 괄호의 값 (3) | 2023.07.21 |
[백준 알고리즘]23309번 자바(Java) 철도공사 (2) | 2023.07.21 |
[백준 알고리즘] 12904번 자바(Java) A와 B (0) | 2023.07.13 |