백준 12716: 돌다리 [Java] - 포포

문제

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N\(N\)번 돌 위에, 주미는 M\(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B\(A, B\) 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A\(A\)나 B\(B\)만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A\(A\)배나 B\(B\)배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

입력

입력의 첫 줄에 스카이 콩콩의 힘 A\(A\)와 B\(B\), 그리고 동규의 현재위치 N\(N\), 주미의 현재 위치 M\(M\)이 주어진다. (단, 2≤A,B≤30\(2 \le A, B \le 30\) 이고  0≤N,M≤100,000\(0 \le N, M \le 100,000\))

출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

---

내 제출

package com.company.ch9BFS;

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

public class No12761 {
    static int a, b, n, m;
    static int[] arr;
    static Queue<Point> qu;
    static boolean[] visit;
    static int[] dx = {1, -1, a, -a, b, -b};
    static int count;
    public static void main(String[] args) throws IOException {

        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(" "));
        count = 0;
        qu = new LinkedList<>();
        arr = new int[100001];
        visit = new boolean[100001];
        /**
         * 좌 우로 한 칸 이동 가능
         * 좌 우로 a,b 만큼 이동 가능
         * 우로 현재 위치 * (a || b) 배 만큼 이동 가능
         */

        bfs();
        System.out.println(count);
    }

    private static void bfs() {
        qu.offer(new Point(n, 0));
        visit[n] = true;

        while (!qu.isEmpty()) {
            Point p = qu.poll();

            if(p.x == m){
                count = p.y;
                return;
            }
            if(p.x + 1 < 100001 && !visit[p.x+1]){
                visit[p.x+1] = true;
                qu.offer(new Point(p.x+1, p.y+1));
            }
            if(p.x - 1 >=0 && !visit[p.x-1]) {
                visit[p.x-1] = true;
                qu.offer(new Point(p.x-1, p.y+1));
            }
            if(p.x + a <100001 && !visit[p.x+a]) {
                visit[p.x+a] = true;
                qu.offer(new Point(p.x+a, p.y+1));
            }
            if(p.x - a >=0 && !visit[p.x-a]) {
                visit[p.x-a] = true;
                qu.offer(new Point(p.x-a, p.y+1));
            }

            if(p.x + b < 100001 && !visit[p.x+b]){
                visit[p.x+b] = true;
                qu.offer(new Point(p.x+b, p.y+1));
            }
            if(p.x - b >=0 && !visit[p.x-b]) {
                visit[p.x-b] = true;
                qu.offer(new Point(p.x-b, p.y+1));
            }

            if(p.x * a < 100001 && !visit[p.x*a]){
                visit[p.x*a] = true;
                qu.offer(new Point(p.x * a, p.y+1));
            }
            if(p.x * b < 100001 && !visit[p.x*b]){
                visit[p.x*b] = true;
                qu.offer(new Point(p.x * b, p.y+1));
            }
        }
    }
    static class Point{
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

코드를 적으면서 비슷한 if문을 8개 작성했더니 게슈탈트 붕괴가 왔다. 
아무튼 코드를 작성하고 백준에 있는 테스트 케이스는 잘 통과한 것을 확인했다.

예제 입력 1 

2 3 1 20

예제 출력 1 

4

예제 입력 2 

3 7 2 98500

예제 출력 2 

10

 

탐색을 처음 풀었을 때, 이 돌다리 문제와 비슷한 유형의 문제를 접했는데 그 당시에는 해결이 어려워 블로그에서 풀이를 참고했었다.

지금은 잘 풀게 되어서 뿌듯하다는 얘기가 아니라,,   그 블로그는 풀이와 더불어 반례를 찾는 방법을 간단히 포스팅하였다. 
많은 사람들의 풀이가 0에서 출발하여 100,000 으로 도달하는 경계값 테스트는 잘 통과하지만,
100,000에서 0으로 이동하는 경우는 오답이 종종 나온다고 한다.
근데 나는 Index out of bound라는 런타임 에러가 발생했고 if문 8개 중 숨은 +- 부호 오타를 발견해서 고칠 수 있었다..하하

---