(JAVA) [BOJ]백준 5014번, 스타트링크

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

5014번: 스타트링크

5014, 스타트링크

[ 난이도 : 실버 1 ]

이번 문제는 BFS(너비 우선 탐색)을 사용해서 풀어보겠다.

 

문제를 이해하는데 시간이 더 오래 걸린 문제이다 : )그치만 이해하면 쉽게 풀 수 있다 !

# Process

input

: 길게 쓰여진 문제를 풀이해보면 이렇다.

 

스타트링크는 총 F층

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

강호가 지금 있는 곳은 S층

 

즉, 배열의 크기는 F 로 설정하고 시작 좌표는 S, 목표 좌표는 G 이라고 이해할 수 있다.

U 와 D 는 플러스 & 마이너스 폭이다.

static int F, S, G, U, D;
static int[] dist;

static void input() 
{
    F = scan.nextInt(); // 총 F층
    S = scan.nextInt(); // 강호가 있는 곳
    G = scan.nextInt(); // 목표
    U = scan.nextInt(); // 위로
    D = scan.nextInt(); // 아래로

    dist = new int[F+1];
}

 

BFS

: 위에서 입력받은 값을 기반으로 BFS 를 통해 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최소값을 구해보자.

BFS 풀이는 거의 비슷한 것 같다. 기존과 다르게 U 와 D 로 예외처리만 해주면 쉽게 답을 구할 수 있다.

static void pro() 
{
   bfs(S);
   if(dist[G] == -1)
        System.out.println("use the stairs");
    else
        System.out.println(dist[G]);
}

static void bfs(int start)
{
    for(int i=1;i<=F;i++) dist[i] = -1;

    dist[start] = 0;

    Queue<Integer> Q = new LinkedList<>();
    Q.add(start);

    while(!Q.isEmpty())
    {
        int x = Q.poll();

        if(x+U <= F && dist[x+U] == -1)
        {
            Q.add(x+U);
            dist[x+U] = dist[x] + 1;
        }

        if(x-D > 0 && dist[x-D] == -1)
        {
            Q.add(x-D);
            dist[x-D] = dist[x] + 1;
        }
    }
}

 

전체 코드

static int F, S, G, U, D;
static int[] dist;

static void input() 
{
    F = scan.nextInt(); // 총 F층
    S = scan.nextInt(); // 강호가 있는 곳
    G = scan.nextInt(); // 목표
    U = scan.nextInt(); // 위로
    D = scan.nextInt(); // 아래로

    dist = new int[F+1];
}

static void pro() 
{
   bfs(S);
   if(dist[G] == -1)
        System.out.println("use the stairs");
    else
        System.out.println(dist[G]);
}

static void bfs(int start)
{
    for(int i=1;i<=F;i++) dist[i] = -1;

    dist[start] = 0;

    Queue<Integer> Q = new LinkedList<>();
    Q.add(start);

    while(!Q.isEmpty())
    {
        int x = Q.poll();

        if(x+U <= F && dist[x+U] == -1)
        {
            Q.add(x+U);
            dist[x+U] = dist[x] + 1;
        }

        if(x-D > 0 && dist[x-D] == -1)
        {
            Q.add(x-D);
            dist[x-D] = dist[x] + 1;
        }
    }
}

public static void main(String[] args) 
{
    input();
    pro();
}