[BaekJoon] 5014 스타트링크

1.  문제 링크

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

2.  문제

요약

• 총 F층으로 이루어진 고층 건물에 스타트링크가 있는 곳의 위치는 G층입니다.
• 현재 강호가 있는 층은 S층이고 엘리베이터를 타고 G층으로 이동하는데, 엘리베이터에는 버튼이 2개 있습니다.
• U버튼은 U층을 위로 가는 버튼, D버튼은 아래로 D층을 가는 버튼입니다.
• 강호가 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1000000보다 작거나 같은 F, 1보다 크거나 같고 F보다 작거나 같은 S, G, 0보다 크거나 같고 1000000보다 작거나 같은 U, D가 주어집니다.
  • 건물은 1층부터 시작하고 가장 높은 층은 F층입니다.
• 출력: 첫 번째 줄에 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력합니다. 만약 엘리베이터로 이동할 수 없다면 "use the stairs"를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[] list;
	public String getMinPressNum(int current, int target, int up, int down) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(current);
		list[current] = 1;
		while(!queue.isEmpty()) {
			int cur_point = queue.poll();
			if(cur_point == target) {
				return Integer.toString(list[target] - 1);
			}
			if(cur_point + up < list.length && list[cur_point + up] == 0) {
				queue.offer(cur_point + up);
				list[cur_point + up] = list[cur_point] + 1;
			}
			if(cur_point - down > 0 && list[cur_point - down] == 0) {
				queue.offer(cur_point - down);
				list[cur_point - down] = list[cur_point] + 1;
			}
		}
		return "use the stairs";
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int height = Integer.parseInt(input[0]);
		list = new int[height + 1];
		int current = Integer.parseInt(input[1]);
		int target = Integer.parseInt(input[2]);
		int up = Integer.parseInt(input[3]);
		int down = Integer.parseInt(input[4]);
		br.close();
		Main m = new Main();
		bw.write(m.getMinPressNum(current, target, up, down) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• Queue에 출발 층을 넣어주고 출발 층에서 U 버튼을 눌러 U층 위로 올라가는 경우와 D 버튼을 눌러 D층 아래로 내려가는 경우에 대해 각각 Queue에 넣어줍니다.
• Queue에서 한 층씩 꺼내면서 해당 층에서 U 버튼을 눌러 U층 위로 올라가는 경우와 D 버튼을 눌러 D층 아래로 내려가는 경우에 대해 각각 Queue에 넣어주는 작업을 반복합니다.
• 만약 Queue에서 꺼낸 층이 목표 층과 같다면 그 때까지 누른 횟수를 출력합니다.
• 만약 Queue가 다 비워지기 전까지 목표 층에 도달하지 못했다면 목표 층에 도달할 수 없다는 뜻이므로 use the stairs를 출력합니다.

public String getMinPressNum(int current, int target, int up, int down) {
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.offer(current);
	list[current] = 1;
	while(!queue.isEmpty()) {
		int cur_point = queue.poll();
		if(cur_point == target) {
			return Integer.toString(list[target] - 1);
		}
		if(cur_point + up < list.length && list[cur_point + up] == 0) {
			queue.offer(cur_point + up);
			list[cur_point + up] = list[cur_point] + 1;
		}
		if(cur_point - down > 0 && list[cur_point - down] == 0) {
			queue.offer(cur_point - down);
			list[cur_point - down] = list[cur_point] + 1;
		}
	}
	return "use the stairs";
}

1. (주어진 F + 1) 크기의 배열을 생성하고 주어진 S, G, U, D를 이용하여 BFS 알고리즘을 통해 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 구합니다.
   1. Queue를 생성하고 Queue에 현재 층인 S를 넣어줍니다.
   2. 현재 층 위치에 해당하는 배열 값을 1로 변경해줍니다.
      • 위에서 생성한 배열은 해당 층에 도달할 때까지 버튼을 누른 횟수를 의미합니다.
   3. Queue가 비워지기 전까지 반복문을 돌면서 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 구합니다.
      1. Queue에서 층을 하나 뽑아냅니다.
      2. 현재 층이 F층이라면 반복문을 끝내고 F층 위치에 해당하는 배열값을 출력합니다.
      3. 그렇지 않다면 (현재 층 + U)가 F층 안에 존재하고 해당 층 위치의 배열값이 0이라면 Queue에 해당 층을 넣어주고 해당 층 위치의 배열값을 (현재 층 위치의 배열값 + 1)로 변경해줍니다.
      4. 또한 (현재 층 - D)가 F층 안에 존재하고 해당 층 위치의 배열값이 0이라면 Queue에 해당 층을 넣어주고 해당 층 위치의 배열값을 (현재 층 위치의 배열값 + 1)로 변경해줍니다.
   4. 3번 반복문이 끝날 때까지 F층 위치에 해당하는 배열값을 출력하지 않았다면 F층에 도달할 수 없다는 뜻이므로 use the stairs를 출력합니다.