[Gold V] 숨바꼭질 3 - 13549

JYC·2024년 9월 18일

백준 알고리즘 문제 자바

[BAEKJOON]

목록 보기

99/102

문제 링크

성능 요약

메모리: 86944 KB, 시간: 220 ms

분류

0-1 너비 우선 탐색, 너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2024년 9월 18일 21:31:26

문제 설명

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

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

입력

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

출력

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

풀이(BFS)

여러 블로그를 참고해 해결했다...

각각의 경우(순간이동, +1, -1)를 따져가며 최소를 구한다는 쉬운 풀이임에도 틀렸습니다. 가 나올 수 있는 문제이다.

못 푼 이유

내게 특히 문제가 됐던 반례는

입력: 4 6
출력: 1

위 케이스이다.

답은 분명 1이지만, 방문 여부를 어떻게 처리하느냐에 따라 코드 출력이 2가 나온다.

먼저 답이 1이 나오는 경우는 4 -> 3 -> 6 이 경우이다.
하지만 필자의 코드에서는 자꾸 출력이 2가 나왔는데, 이는 while문에서 4 -> 5 -> 6을 먼저 처리하고 4 -> 3 -> 6를 나중에 처리했기 때문이다.

4 -> 5 -> 6 을 먼저 처리하면 방문 여부 확인 배열에서는 6이 방문했다고 바뀌게 될 것이다.
그 후로 어떤 답이 들어오든 6은 이미 방문했다고 나오므로 최소 시간은 바뀌지 않게 되는 것이다.

위 문제를 해결하지 못해 다른 블로그를 참고했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Node{
	int x;
	int time;
	
	public Node(int x,int time) {
		this.x=x;
		this.time=time;
	}
}

public class Main {
    //bfs 풀이
	static int n;
	static int k;
	static boolean[] check = new boolean[100001];
	static int min_num = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		if(n>=k) { //n이 더 크거나 같으면 비교 의미 X
			System.out.println(n-k);
		}
		else {
			bfs(n);
			System.out.println(min_num);
		}
	}
	
	public static void bfs(int num) {
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(new Node(num,0));
		while(!queue.isEmpty()) {
			Node node=queue.poll();
			check[node.x]=true;
			
			if(node.x==k) { //최소 시간 찾기
				min_num = Math.min(node.time,min_num);
			}
			
            //순간이동 가능할 경우 (시간 0초 소요)
			if(node.x *2 <= 100000 && check[node.x*2]==false) {
				queue.add(new Node(node.x*2,node.time));
			}
            
            //+1 가능할 경우 (시간 1초 소요)
			if(node.x +1<=100000 && check[node.x+1]==false) {
				queue.add(new Node(node.x+1,node.time+1));
			}
            
            //-1 가능할 경우 (시간 1초 소요)
			if(node.x-1>=0 && check[node.x-1]==false) {
				queue.add(new Node(node.x-1,node.time+1));
			}
		}
	}
}