알고리즘/백준

1697_숨바꼭질 * (맞았는데 다시 풀면 또 틀리려나;)

베리영young 2024. 8. 22. 01:38

사용 알고리즘: bfs

사용 언어: java

 

package ssafyAlgorithm;

import java.util.*;
import java.io.*;

public class Main_1697_숨바꼭질 {
	static int[] dp = new int[100001];
	static int a,b;
	static final int inf = 987654;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        Arrays.fill(dp, inf);
        
        dp[a] = 0;
        
        Queue<Integer> q = new ArrayDeque<>();
        q.add(a);
        
        while(!q.isEmpty()) {
        	int cur = q.poll();
        	
//        	System.out.println(cur+" "+dp[7]+" "+dp[8]);
        	
//        	if(cur == b) {
//        		break;
//        	}
        	
        	if(cur-1 >= 0 && dp[cur-1] == inf) {
        		dp[cur-1] = dp[cur] + 1;
        		q.add(cur-1);
        	}
        	
        	if(cur+1 < 100001 && dp[cur+1] == inf) {
        		dp[cur+1] = dp[cur] + 1;
        		q.add(cur+1);
        	}
        	
        	if(cur*2 < 100001 && dp[cur*2] == inf) {
        		dp[cur*2] = dp[cur] + 1;
        		q.add(cur*2);
        	}
        }
        
        System.out.println(dp[b]);
    }
    
}

 

 

하... 별 것도 아닌데 몇 번을 틀렸는지 모르겠음..... 하하하하하하

'알고리즘 > 백준' 카테고리의 다른 글

1238_파티 * (문제 자체를 다시 풀기 보다는, 풀이 방법을 생각해내기)  (1) 2024.08.23
15961_회전 초밥  (0) 2024.08.22
15683_감시  (0) 2024.08.20
13023_ABCDE  (0) 2024.08.20
1753_최단경로  (0) 2024.08.20