[BOJ 1103] 스타트링크

[BOJ 1103] 스타트링크

 

1. 문제 : https://www.acmicpc.net/problem/1103

 

2. 풀이

+, - 둘 다 queue에 넣기

직접 더하거나 뺀 후 비교하지 않고 더한 / 뺀 값으로 비교하기

 

3. 코드

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 스타트링크 {


    static int f, s, g, u, d;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        f = scan.nextInt();
        s = scan.nextInt();
        g = scan.nextInt();
        u = scan.nextInt();
        d = scan.nextInt();

        visited = new boolean[f + 1];
        int result = bfs();

        if(result < 0) System.out.println("use the stairs");
        else System.out.println(result);
    }

    public static int bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(s, 0));
        visited[s] = true;

        while(!q.isEmpty()) {
            Node current = q.poll();
            if(current.x == g) return current.cost;

            if(current.x + u <= f && visited[current.x + u] == false) {
                q.offer(new Node(current.x + u, current.cost + 1));
                visited[current.x + u] = true;
            }
            if(current.x - d >= 1 && visited[current.x - d] == false) {
                q.offer(new Node(current.x - d, current.cost + 1));
                visited[current.x - d] = true;
            }
        }
        return -1;
    }

    public static class Node {
        int x;
        int cost;

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