[백준/JAVA] 5014번: 스타트링크

🔺 문제

5014번: 스타트링크

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int F,S,G,U,D;
    static int[] A;
    static int cnt = 0;
    static boolean isEnd = false;
    
    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());
        S = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        U = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        
        A = new int[F + 1];
        bfs(S);
        
        System.out.println(isEnd ? cnt : "use the stairs");
    }
    
    private static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        A[num] = 1; // 시작점 방문 표시
        
        while(!queue.isEmpty()) {
            int now = queue.poll(); // 현재 위치
            
            if(now == G) { // 현재 위치 = 도착점이면 종료
                isEnd = true;
                cnt = A[now] - 1; // 맨 처음 거 빼기
                return;
            }
            
            if(now + U <= F) { // 위층으로 올라갔을 때, F보다 작거나 같은 경우
                if(A[now + U] == 0) { // 방문하지 않은 지점이라면
                    A[now + U] = A[now] + 1; // 올라가서 값 업데이트
                    queue.add(now + U);
                }
            }
            
            if(now - D > 0) { // 아래층으로 내려갔을 때, 0보다 큰 경우
                if(A[now - D] == 0) { // 방문하지 않은 지점이라면
                    A[now - D] = A[now] + 1; // 내려가서 값 어데이트
                    queue.add(now - D);
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ BFS
1) 현재 위치 = 목표점 ⇨ 출력

2) 현재 위치 + 위로 이동한 값 <= 최고층 && 방문 X
    ⇨ [현재층 + 위쪽 이동]을 [현재층] + 1 값으로 업데이트하고 큐에 추가

3) 현재 위치 - 아래로 이동한 값 > 0 && 방문 X
    ⇨ [현재층 + 아래쪽 이동]을 [현재층] + 1 값으로 업데이트하고 큐에 추가

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

위로 올라간 횟수와 아래로 내려간 횟수의 조합..으로 문제를 풀 생각했는데

그냥 BFS로 탐색하는 문제였다...

 

인접 행렬 사용하지 않고, 그냥 배열을 사용하신 것도 기억해둬야할듯.

방문 처리를 배열의 값에 1을 더하는 식으로 하는 것도!

나 만날 이런 문제에서 감 못 잡음ㅠ

 

 

 

1회독	2회독	3회독	4회독	5회독
V	240508

 

 

(+ 240508 2회독 : 33900KB, 188ms)

위 아래로 이동한 칸을 큐에 추가하며 누르는 버튼 수를 구하면 된다는 갈피는 잡았다만

누른 적 없는 칸을 큐에 추가해야 한다는 조건을 빠뜨려서 헤맸다..

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int F,S,G,U,D;
    static int[] arr;
 
    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());   // 건물 총 층
        S = Integer.parseInt(st.nextToken());   // 강호 층
        G = Integer.parseInt(st.nextToken());   // 회사 층 (=목표 층)
        U = Integer.parseInt(st.nextToken());   // 위
        D = Integer.parseInt(st.nextToken());   // 아래
 
        arr = new int[F + 1];
        int answer = bfs();
 
        System.out.println(answer == -1 ? "use the stairs" : answer);
    }
 
    private static int bfs() {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(S);
 
        arr[S] = 1;    // 강호 층 버튼 누르기
 
        while(!q.isEmpty()) {
            int now = q.poll();
 
            if(now == G) {  // 목표 층 G층 도착 시
                return arr[now] - 1;
            }
 
            if(now + U <= F) {  // 최고층 F층 아래에 있고
                if(arr[now + U] == 0) { // 방문한 적 없는 경우
                    arr[now + U] = arr[now] + 1;
                    q.add(now + U);
                }
            }
            if(now - D >= 1) {  // 최저층 1층 이상에 있고
                if(arr[now - D] == 0) { // 방문한 적 없는 경우
                    arr[now - D] = arr[now] + 1;
                    q.add(now - D);
                }
            }
        }
 
        return -1;  // 목표 층 도착 못 할 시 -1 출력
    }
}
 

 

 

---

(참고)

✔ 풀이 참고

[BOJ] 백준 5014 - 스타트링크 (자바)

[백준 5014] 스타트링크 <Java>