[BOJ] 12761 돌다리

돌다리

풀이

• bfs로 풀이
• int[] map = new int[100001]; map배열을 선언 후, 탐색 방향이 8개 이므로 int[] dx = { 1, -1, A, -A, B, -B } 로 6개 경우 탐색 후, 현 위치의 A배나 B배의 위치로 이동 하는 두개의 경우 탐색함.
• map[이동할 곳] = map[현재위치]+1 로 구현하여 map[M] 까지의 최소 이동 횟수 구함.

코드

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

public class BOJ12761 {
    static int[] map = new int[100001];
    static int A, B, N, M;
    
     
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        bfs(N);
        System.out.println(map[M]);
    }


    private static void bfs(int x) {
        int[] dx = { 1, -1, A, -A, B, -B };
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cur == M) {
                break;
            }
            for (int i = 0; i < 6; i++) {
                int nx = cur + dx[i];
                if (nx >= 0 && nx <= 100000 && map[nx]==0) {
                    map[nx] = map[cur] + 1;
                    queue.offer(nx);
                }
            }
            if (cur * A >= 0 && cur * A <= 100000 && map[cur * A]==0) {
                map[cur * A] = map[cur] + 1;
                queue.offer(cur * A);
            }
            if (cur * B >= 0 && cur * B <= 100000 && map[cur * B]==0) {
                map[cur * B] = map[cur] + 1;
                queue.offer(cur * B);
            }
        }
        
    }
}