[백준] 5014번 스타트링크 JAVA (자바) 풀이

 

 

문제 5014번 (bfs)

 :  건물 총 F층

    스타트링크가 있는 곳의 위치는 G층

    현위치 S층

 

 :  엘리베이터는 버튼이 2개밖에 없다
    U버튼은 위로, D버튼은 아래로 가는 버튼

 

 :  G층에 도착하려면 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성

    (만약, G층에 갈 수 없다면, "use the stairs"를 출력)

 

 

 [입력]

 :  첫째 줄에 F, S, G, U, D (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 

 

 

[출력]

 :  S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력 

    (갈 수 없다면, "use the stairs")

 

[설명]

 

1. count 가 아닌 arr 배열 이용하기

 

2. void가 아닌 int 사용

• void를 사용하려면 return이 아닌 System.out.println으로 바로 출력해야 한다
• return을 사용하기 위해서 int로 변경

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int F, start, end, up, down, count,arr[];
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        F = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        up = Integer.parseInt(st.nextToken());
        down = Integer.parseInt(st.nextToken());
        count =0;
        visit = new boolean[F+1];
        arr = new int[F+1];
      
        if(bfs()==-1){
            System.out.println("use the stairs");
        }
        else
            System.out.println(arr[end]);
       
    }
    
    static int bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visit[start]=true;
        
        int[] cal = {up, -down}; 
        
        while(!q.isEmpty()){
            int p = q.poll();
            if(p==end){
                return arr[p];
            }
            for(int i=0; i<2;i++){
                int np = p + cal[i];
                if(0<np&&np<=F&&!visit[np]){
                    visit[np] = true;
                    q.add(np);
                    arr[np]=arr[p]+1;
                }
            }
        }
        return -1;
    }
}

 

 [해설]
     

 :  static int F, start, end, up, down, arr[];  입력
    static boolean visit[];
    

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());
    F = Integer.parseInt(st.nextToken());  건물 층수
    start = Integer.parseInt(st.nextToken());  현재 내위치
    end = Integer.parseInt(st.nextToken());  가야할 층
    up = Integer.parseInt(st.nextToken());  up할 수 있는 층수
    down = Integer.parseInt(st.nextToken());  down할 수 있는 층수

 :  visit = new boolean[F+1];  bfs 하기 전에 visit 초기화
    arr = new int[F+1];  count 대신
      
 :  if(bfs()==-1){  bfs 돌려서 -1나오면 갈 수 없는 층
            System.out.println("use the stairs");
    }
    else  bfs 돌려서 특정 값이 나온다는 것은 arr[end]이
            System.out.println(arr[end]);
    }
    

 :  static int bfs(){  bfs 시작
        Queue<Integer> q = new LinkedList<>();  큐선언
        q.add(start);  큐에 start 추가
        visit[start]=true;  현위치 방문처리
        
        int[] cal = {up, -down};  up이랑 down 저장할 수 있는 배열
        
        while(!q.isEmpty()){
            int p = q.poll();  큐에서 뽑기
            if(p==end){  목표지점 도달하면 종료
                return arr[p];  
            }
            for(int i=0; i<2;i++){  움직일 수 있는 방향 두가지
                int np = p + cal[i];  현위치에서 up하거나 down하거나
                if(0<np&&np<=F&&!visit[np]){  층 안에 있으면서 방문하지 않음 
                    visit[np] = true;  방문처리하고
                    q.add(np);  큐에 추가
                    arr[np]=arr[p]+1;  해당 층에 count
                }
            }
        }
        return -1;  층 갈 수 없다면 -1
    }


   

 

      

이제 풀어보러 갈께요 :)

 

 

 

 

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

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *