[알고리즘 / 백준] 5014 - 스타트링크

www.acmicpc.net/problem/5014

5014번: 스타트링크

 

문제는 위와 같으며, 주어지는 층수 정보를 각각 변수에 저장한 뒤 시작 위치부터 위, 아래로 이동하는 경우를 확인하며 BFS 방식을 통해 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq


# 처음 위치부터 위, 아래로 이동하여 도착 위치에 도달할 때까지 누른 버튼 수 반환
def bfs(start):
    queue = []
    heapq.heappush(queue, [0, start])  # 우선순위 큐를 만들어서 [현재 층까지 오는데 누른 버튼의 수, 현재 층] 형태의 데이터를 저장

    visited = [False] * (f + 1)  # 각 층을 방문했는지 안했는지 확인하는 배열을 생성하고
    visited[start] = True  # 출발 층을 방문한 것으로 처리

	# 더 이상 이동할 층이 없을 때까지 반복
    while queue:
        cnt, current_floor = heapq.heappop(queue)

        # 현재 층과 도착 층이 같은 경우
        if current_floor == g:
            return cnt  # 지금까지 누른 버튼 수 반환

        # 위로 올라가는 경우
        next_up_floor = current_floor + u

        if 0 < next_up_floor <= f and not visited[next_up_floor]:  # 위로 이동하는 층이 건물 내에 존재하면서 아직 방문하지 않은 경우
            heapq.heappush(queue, [cnt + 1, next_up_floor])  # [다음 층까지 이동하는데 누른 버튼 수(현재 위치까지 이동하는데 누른 버튼 수 + 1), 다음 층 수] 데이터를 저장하고
            visited[next_up_floor] = True  # 다음 층을 방문한 것으로 처리

        # 아래로 내려가는 경우
        next_down_floor = current_floor - d

        if 0 < next_down_floor <= f and not visited[next_down_floor]:
            heapq.heappush(queue, [cnt + 1, next_down_floor])
            visited[next_down_floor] = True

    return -1  # 도착 층에 도달하지 못하고 더 이상 이동할 층이 없는 경우 -1 반환


f, s, g, u, d = map(int, stdin.readline().split())

result = bfs(s)
if result == -1:
    print("use the stairs")
else:
    print(result)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	// 주어지는 층수 정보 저장
    private static int f;
    private static int s;
    private static int g;
    private static int u;
    private static int d;

    public static void main(String[] args) throws Exception {
        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());

        int result = bfs();
        if (result == -1) {
            System.out.println("use the stairs");
        } else {
            System.out.println(result);
        }
    }

    private static int bfs() {
    	// 이동할 수 있는 층 정보를 저장하는 우선순위 큐를 만들고
        // [현재 층까지 이동하는데 누른 버튼 수, 현재 층 수] 데이터를 저장하는데
        // "현재 층까지 이동하는데 누른 버튼 수"를 기준으로 우선순위를 지정
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] t1, int[] t2) {
                return t1[0] - t2[0];
            }
        });
        queue.offer(new int[]{0, s});  // 시작 위치를 우선 순위 큐에 추가

        boolean[] visited = new boolean[f + 1];  // 각 층을 방문했는지 파악할 수 있는 배열을 생성
        visited[s] = true;  // 시작 위치를 방문한 것으로 처리

		// 더 이상 방문할 수 있는 층이 없을 때까지 반복
        while (!queue.isEmpty()) {
            int[] current = queue.poll();

			// 현재 층 수가 도착 층 수와 같다면
            if (current[1] == g) {
                return current[0];  // 현재 층(도착 층)까지 누른 버튼 수를 반환
            }

            // 위로 올라가는 경우
            int next_up_floor = current[1] + u;

            if (next_up_floor > 0 && next_up_floor <= f && !visited[next_up_floor]) {
                queue.offer(new int[]{current[0] + 1, next_up_floor});
                visited[next_up_floor] = true;
            }

            // 아래로 내려가는 경우
            int next_down_floor = current[1] - d;
            if (next_down_floor > 0 && next_down_floor <= f && !visited[next_down_floor]) {
                queue.offer(new int[]{current[0] + 1, next_down_floor});
                visited[next_down_floor] = true;
            }
        }

        return -1;
    }
}