[백준] 5014 스타트링크(Java)

문제링크

https://www.acmicpc.net/problem/5014

문제분석

• S층부터 시작해 G층까지 이동해야 한다.
• 엘레베이터의 이동은 U, D 2가지 경우이다.
  • 위로 이동 : U칸만큼 위로 이동
  • 아래로 이동 : D칸만큼 아래로 이동
  • 주의 : 계산값에 해당하는 층이 없다면, 움직이지 않는다.

입력

• F(건물의 층수), S(강호의 처음 위치), G(목표 층), U(위로 이동 층수), D(아래로 이동 층수)
• 1 <= S,G <=F <=1000000
• 0 <= U, D <= 1000000

출력

• 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 최솟값
• 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

풀이

• 엘리베이터를 표현하기 위해 클래스를 선언

class Elevator{
    int current; //현재 층
    int buttonCount; // 지금까지 눌린 버튼 수
 
    void U(int step, int top){ // 위로 이동
        if(current+step <= top){ // 목표층이 존재할 때만 이동
            current+=step;
        }
    }

    void D(int step){ //아래로 이동
        if(current-step>=1){ // 목표층이 존재할 때만 이동
            current-=step;
        }
    }
}

• 입력된 값에 대해 BFS 수행
  • 중복 계산을 막기 위해 visited 배열을 선언한다.
  • 현재 층수가 목표층이면 반복문 중단
  • 현재 층수에서 U, D 연산을 수행한다.
  • 연산 결과가 처음 방문하는 층이면, 큐에 넣는다.

private static int BFS(int f, int s, int g, int u, int d) {
        int result = -1;

        Queue<Elevator> queue = new LinkedList<>();

        //현재층을 체크하고, 큐에 삽입
        visited[s] = true;
        queue.offer(new Elevator(s, 0));

        while(!queue.isEmpty()){
            Elevator now = queue.poll();
            int current = now.getCurrent();
            int currentButtonCount = now.getButtonCount();

            //현재 층이 목표층이면, 반복문 중단
            if(current==g){
                result=currentButtonCount;
                break;
            }

            //U, D연산을 수행한다.
            Elevator up = new Elevator(current, currentButtonCount+1);
            up.U(u, f);
            Elevator down = new Elevator(current, currentButtonCount+1);
            down.D(d);

            //이전에 방문했던 층이 아니면, 체크 후 큐에 삽입
            if(!visited[up.getCurrent()]) {
                visited[up.getCurrent()] = true;
                queue.offer(up);
            }
            if(!visited[down.getCurrent()]){
                visited[down.getCurrent()] = true;
                queue.offer(down);
            }
        }

        return result;
    }

전체 코드

import java.util.*;

class Elevator{
    int current;//현재 층
    int buttonCount;// 지금까지 눌린 버튼 수

    public Elevator(int current, int buttonCount) {
        this.current = current;
        this.buttonCount = buttonCount;
    }

    void U(int step, int top){// 위로 이동
        if(current+step <= top){// 목표층이 존재할 때만 이동
            current+=step;
        }
    }

    void D(int step){//아래로 이동
        if(current-step>=1){// 목표층이 존재할 때만 이동
            current-=step;
        }
    }

    public int getCurrent() {
        return current;
    }

    public int getButtonCount() {
        return buttonCount;
    }
}

public class Main {
    // BFS의 중복 계산을 막기위한 체크배열
    static boolean[] visited;

    public static void main(String[] args){
        //입력을 받는다.
        Scanner scanner = new Scanner(System.in);
        int F = scanner.nextInt();
        int S = scanner.nextInt();
        int G = scanner.nextInt();
        int U = scanner.nextInt();
        int D = scanner.nextInt();

        //건물의 층수 만큼 체크배열 생성
        visited = new boolean[F+1];

        int answer = -1;

        //BFS 탐색
        answer = BFS(F, S, G, U, D);

        //목표층에 도달할 수 없다면, use the stairs 출력
        if(answer==-1) System.out.println("use the stairs");
        else System.out.println(answer);
    }

    private static int BFS(int f, int s, int g, int u, int d) {
        int result = -1;

        Queue<Elevator> queue = new LinkedList<>();

        //현재층을 체크하고, 큐에 삽입
        visited[s] = true;
        queue.offer(new Elevator(s, 0));

        while(!queue.isEmpty()){
            Elevator now = queue.poll();
            int current = now.getCurrent();
            int currentButtonCount = now.getButtonCount();

            //현재 층이 목표층이면, 반복문 중단
            if(current==g){
                result=currentButtonCount;
                break;
            }

            //U, D연산을 수행한다.
            Elevator up = new Elevator(current, currentButtonCount+1);
            up.U(u, f);
            Elevator down = new Elevator(current, currentButtonCount+1);
            down.D(d);

            //이전에 방문했던 층이 아니면, 체크 후 큐에 삽입
            if(!visited[up.getCurrent()]) {
                visited[up.getCurrent()] = true;
                queue.offer(up);
            }
            if(!visited[down.getCurrent()]){
                visited[down.getCurrent()] = true;
                queue.offer(down);
            }
        }

        return result;
    }
}