백준 12761. 돌다리 :: 돼지개발자

출처 : https://www.acmicpc.net/problem/12761

"DP를 사용할 때, 부등호를 조심하자."

해당 문제를 BFS를 이용해 풀었다. 대충 계산해보아도 총 100,001 개의 지점이 있고, 각 지점마다 갈 수 있는 경우의 수는 8 가지 이므로 8^100000 이나 되므로(실제로는 이보다 작겠지만) 그냥 단순 탐색으로는 무리가 있고, 메모이제이션을 이용해서 가지치기를 해줘야 했다. 

 지점 A에서 B로 간다고 했을 때, 내가 지점 B까지 가는데 걸린 횟수를 저장하는 것, 단 이때 DP[B] 에 값이 INF 가 아니라면(이미 누군가 방문 했다면) 나보다 지점 A를 더 짧은 횟수 안에 통과했는지를 비교한다. 

if ( dp[B] <= dp[A] + 1 ) continue;

N의 수가 클 때, 항상 주의해야 하며, 테스르를 할 때는 최악의 시간 복잡도가 나올 수 있는 테스트 케이스를 이용하자. DP를 생각했고, BFS에 대해 알면 쉽게 풀 수 있는 문제이다. 

 도착 지점에 가까운 노드가 최소 횟수가 될 가능성이 높다는 가정을 하고  PriorityQueue를 사용해서 목표 지점과의 거리차를 기준으로 우선순위를 부여하면 좀더 빨라지지 않을까? 라는 생각을 한번 해봤는데, 실제로 해보진 않았다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Main {
    static int A,B;
    static int N,M;
    static int[] dp = new int[100001];
    static final int INF = 1000000;
    static Scanner sc = new Scanner(System.in);
    static Queue<Integer> q = new LinkedList<>();
    
    public static void main(String[] args)  {
        
        A = sc.nextInt();
        B = sc.nextInt();
        N = sc.nextInt();
        M = sc.nextInt();
        
        Arrays.fill(dp, INF);
        
        dp[N] = 0;
        q.add(N);
        
        while(!q.isEmpty()) {
            
            int cur = q.poll();
            
            if(cur == M) {
                break;
            }
            
            int[] temp = move(cur);
            
            for (int i = 0; i < 8; i++) {
                int next = temp[i];
                if(next < 0 || next > 100000 || dp[next] <= dp[cur]+1 )
                    continue;
                dp[next] = dp[cur]+1;
                q.add(next);
            }
        }
        
        System.out.println(dp[M]);
    }
    
    static int[] move(int x) {
        int[] temp = new int[8];
        temp[0] = x+1;
        temp[1] = x-1;
        temp[2] = x-A;
        temp[3] = x+A;
        temp[4] = x-B;
        temp[5] = x+B;
        temp[6] = x*A;
        temp[7] = x*B;
        
        return temp;
    }
    
}