[백준] code.plus(BFS 알고리즘,JAVA)5014번, 스타트링크

문제 링크

5014번: 스타트링크

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. S의 위치에서 G에 위치로 이동하는 최소 이동 횟수를 결과로 출력합니다.

2. 올라갈 때에는 U만큼 이동, 내려갈 때에는 D만큼 이동

3. 건물은 1층부터 시작하며 U, D만큼 이동한 후 존재하지 않는 층이면 이동하지 않는다.

4. 해당 층으로 이동할 수 없으면 "use the stair"을 결과로 출력합니다.

 

엘리베이터 올라가는 버튼 클릭

현재 층 + U

 

엘리베이터 내려가는 버튼 클릭

현재 층 - D

 

 

 

엘리베이터의 이동을 S에서 시작하여 G까지 버튼을 누르면서 최소 이동 횟수를 구하는 BFS탐색을 진행하였습니다.

 

※가장 먼저 G에 도착했을 때가 최소 이동 횟수입니다.

 

만약 G까지 도달하지 못한다면 "use the stair"를 출력하도록 하였습니다.

 

 

예제입력 1.

 

F(전체 층) = 10

S(강호 위치) = 1

G(스타트링크 위치) = 10

U(올라가는 가중치) = 2

D(내려가는 가중치) = 1

 

BFS 탐색 시작!

Up

1 + 2 = 3

 

Down

1 - 1 = 0 (해당 층은 건물을 벗어나기 때문에 불가능)

 

다음 탐색

Up

3 + 2 = 5

 

Down

3 - 1 = 2

 

다음 탐색

Up

5 + 2 = 7

2 + 2 = 4

 

Down

5 - 1 = 4(이미 방문)

2 - 1 = 1(이미 방문)

 

다음 탐색

Up

7 + 2 = 9

4 + 2 = 6

 

Down

7 - 1 = 6(이미 방문)

4 - 1 = 3(이미 방문)

 

다음 탐색

Up

9 + 2 = 11(해당 층은 건물을 벗어나기 때문에 불가능)

6 + 2 = 8

 

Down

9 - 1 = 8(이미 방문)

6 - 1 = 5(이미 방문)

 

다음 탐색

Up

8 + 2 = 10(스타트링크 도착!!)

 

버튼 누른 경로 : Up - Down - Up - Up - Up - Up

 

누른 횟수 6을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 F,S,G,U,D를 저장하였습니다.
• S->G이동하는 엘리베이터 최소 누른 횟수를 BFS탐색하는 bfs함수를 실행하였습니다.
• G에 도달시 최소 버튼 누른 횟수, 도달 못할 때 "use the stair"을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 S -> G에 도달하는 최소 버튼 누른 횟수를 BFS탐색하는 함수입니다.
• bfs함수는 G에 도달하면 최소 버튼 누른 횟수, 도달하지 못하면 -1을 반환합니다.

 

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

public class Main {
	//BFS에 Queue에 사용될 클래스
    static class position{
        int floor, count;
        public position(int floor, int count) {
            this.floor = floor;
            this.count = count;
        }
    }
    static int F,S,G,U,D;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        F = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        U = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        int result = bfs();		//BFS 탐색 시작
        if(result == -1)	//G까지 도달 불가능시
            bw.write("use the stairs");
        else	//G까지 도달시
            bw.write(result + "");	//최소 버튼 누른 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //S -> G까지 엘리베이터 이동의 최소 버튼 횟수를 구하는 BFS 함수
    static int bfs(){
        Queue<position> queue = new LinkedList<>();
        boolean[] visited = new boolean[F+1];
        visited[S] = true;	//시작 층 방문 확인
        queue.add(new position(S, 0));	//시작 층 Queue 저장
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int floor = cur.floor;
            int count = cur.count;
            if(floor == G)		//G에 도착시
                return count;
            //Up
            int tempFloor = floor + U;
            if(tempFloor <= F && !visited[tempFloor]){
                visited[tempFloor] = true;
                queue.add(new position(tempFloor,count+1));
            }
            //Down
            tempFloor = floor - D;
            if(tempFloor >= 1 && !visited[tempFloor]){{
                visited[tempFloor] = true;
                queue.add(new position(tempFloor, count+1));
            }}
        }
        return -1;		//G에 도달 불가능시 -1 반환
    }
}