[백준]5014번 : 스타트링크 - 자바(JAVA)

 

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

5014번: 스타트링크

문제 해석

건물은 총 F층으로 이루어져 있으며, 목적지의 위치는 G층이다.

현재 위치는 S층이고 엘리베이터를 타고 이동하려고 한다.

엘리베이터의 버튼은 2가지 위로가는 U버튼과 밑으로가는 D버튼이 있다.

U버튼과 D버튼은 각각 정해진 층수만큼 위 또는 아래로 이동한다.

만약 U버튼이 2이고 D버튼이 1이라면 U버튼을 한번 누를 때마다 위로 2층 D버튼을 한번 누를 때마다 아래로 1층 이동하게 된다.

만약 엘리베이터를 이용할 수 없다면 계단을 이용한다.

 

엘리베이터를 이용할 수 없는 경우

현재위치는 2층인데 목적지가 1층인 상황이며 아래로 내려갈 수 있는 D버튼이 0이라면 엘리베이터를 이용하여 아래로 내려갈 수 없으므로 계단을 이용해야 합니다.

 

---

입력

F, S, G, U, D 각각의 자연수

 

제약조건

S >=1

G <= F <= 1000000

U >= 0

D <= 1000000

---

출력

S층에서 G층에 도달하기 위해 눌러야 하는 버튼수의 최솟값을 출력하고 엘리베이터로 이동할 수 없다면 "use the stairs"를 출력한다.

---

문제 풀이 전 설계

입력값 받기

F, S, G, U, D에 대하여 입력을 받아야 한다.

 

 

핵심 기능

엘리베이터를 이용할 수 없는 경우를 확인하는 기능

버튼을 최소한으로 조작하여 도달할 수 있는 기능

---

풀이하면서 고민해본점

입력은 어떻게 받는것이 효율적일까? (Sacnner vs BufferedReader)

https://junuuu.tistory.com/7?category=968252 

[Java] Scanner 와 BufferedReader의 차이점

출력은 어떻게 하는것이 효율적일까? (System.out.println vs BufferedWriter)

https://blog.naver.com/scyawer/222072629287

자바)System.out.println vs. BufferedReader

 

엘리베이터로 목적지에 도달하기 위해서는 어떻게 할 것인가?

현재 위치와 목적지를 비교하여 현재 위치가 더 낮다면 UP 버튼을 누르고 현재 위치가 더 높다면 DOWN 버튼을 누른다.

 

최소한으로 움직이기 위해서는 위,아래 버튼을 번갈아가면서 누르는 것 보다는 한쪽방향으로 쭉 이동하는게 좋을 것이라고 생각한다.

 

예시

아래로 2칸 위로1칸가는 버튼이 있고 목적지를 가기위해서는 아래로 5칸을 가야한다.

아래, 위를 반복하면서 버튼을 누르면 한번 반복시에 아래로 1칸 이동하기 때문에 10번 버튼을 눌러야 한다.

하지만 아래버튼 3번과 위버튼 1번을 누른다면 5번만에 목적지로 도착할 수 있다.

 

엘리베이터를 이용할 수 없는 경우는 어떤 경우인가?

엘리베이터를 이용할 수 없는 경우

1. 아래버튼을 누를경우 1층보다 낮아지는 경우

 

2. 위버튼을 누를경우 건물의 총 층수(F) 보다 높아지는 경우

 

3. ax + by != 목적지인 경우

우리가 목적지에 도달하기 위해서는 a번의 up버튼을 누르고 b번의 down버튼을 눌러야 한다.

하지만 몇번을 누르더라도 도달할 수 없는 수식이라면 엘리베이터를 이용할 수 없는 경우이다.

예를들어 위로4칸 아래로2칸가는 버튼이 존재하고 현재 10층에 있고 5층이 목적지인 상황이다.

현재층이 목적지보다 높으니 아래로 이동을 한다.(4층까지이동)

현재층이 목적지보다 낮으니 위로 이동을 한다.(8층으로 이동)

현재층이 목적지보다 높으니 아래로 이동을 한다.(4층까지이동)

현재층이 목적지보다 낮으니 위로 이동을 한다.(8층으로 이동)

이런식으로 무한루프에 빠져 방향전환이 계속 발생할 것이다.

 

 

4. 아래로 내려갈 수 없는 경우(아래버튼이 0인경우)

 

5. 위로 올라갈 수 없는 경우(위버튼이 0인경우)

 

간단한 문제라고 생각했지만 생각보다 많은 상황이 그려질꺼 같아서 고민이 많이됩니다.

이런 문제를 풀때는 항상 극한의 상황을 연출해보고 그것을 해결할 수 있는 방안을 찾으려고 합니다.

아래로 2층 위로1층 올라가는 버튼이 있고 목적지는 1층이고 현재6층인 상황이다.

위에서 목적지에 도달하기 위해서는 한쪽방향으로 쭉 이동한 뒤 전환하는게 좋기 때문에 밑으로 쭉 이동할 경우에 아래 버튼을 2번눌러 2층에 도달하게 된다면 엘리베이터를 이용할 수 없는 1번경우에 해당하지만(건물에 0층이 없기 때문) 사실 위버튼을 눌러 1층올라간 후 다시 아래버튼을 누른다면 도달할 수 있다.

따라서 위의 상황을 고려해야 한다.

 

만약에 아래로5층 위로1층 올라가는 버튼이 있고 목적지는 1층이고 현재 2층이라면 아래로는 갈 수 없는 상황이니 위로 올라가야합니다. 이때는 위로 한번 올라갈때마다 아래로 내려갈 수 있는지 확인해야 합니다.

 

만약 현재위치에서 아래로도 내려갈 수 없고 위로도 올라갈 수 없다면 엘리베이터를 이용할 수 없는 경우이며 계단을 이용해야 합니다.

예시) 현재위치는 2층이고 목적지는 3층 총 건물의 층수는 5층인데 엘리베이터의 버튼이 위로 10층, 아래로 10층인 경우

 

계단을 이용해야 하는 경우를 다시 총 정리를 해보자면

1. 현재위치에서 아래로 내려가야 하지만 아래버튼이 0인경우

예시) 현재2층이고 목적지는 1층이지만 아래버튼이 0인경우(2층에서 무한루프)

2. 현재위치에서 위로 올라가야 하지만 위버튼이 0인경우

예시) 현재1층이고 목적지는 2층이지만 위버튼이0인경우(1층에서 무한루프)

3. 위로 아래로 계속 무한루프에 빠지는 경우

예시) 위로4칸 아래로2칸가는 버튼이 존재하고 현재 10층에 있고 5층이 목적지인 경우(4층~8층 무한루프)

4. 아래로 내려갈경우 1층이며 위로 올라갈 경우 꼭대기층을 초과해버리는 경우(둘다 동시에 발생해야 함)

예시) 현재위치는 2층이고 목적지는 3층 총 건물의 층수는 5층인데 엘리베이터의 버튼이 위로 10층, 아래로 10층인 경우

 

 

 

의미있는 변수명,함수명을 지어보자

F, S, G, U, D 대신에 totalFloor, currentLocation, destination, up, down을 사용했다.

 

if분기가 충접되어 많아서 코드 가독성이 떨어지는데 지금이 최선인걸까?

다양한 시나리오가 존재하기 때문에 코드에 if문이 많고 if문안에 if문이 또 그 if문안에 if문이 등장하게 되었다.

3번 중첩되어 가독성이 떨어지는데 이게 최선일지는 아직 잘 모르겠다.

무한루프를 찾는 방법을 개선하게 되어 if문 2번중첩으로 해결

 

무한루프에 빠지는경우 어떻게 알 수 있을까?

목적지에 도달하기 위해서 보통 한뱡항으로 움직이다가 다른방향으로 이동하게 된다면 목적지에 도달할 수 있다.(방향전환 1번)

하지만 한방향으로 움직이다가 1층이나 꼭대기층을 만나게되면 반대방향으로 움직여야하고 다시 그 방향으로 이동해야 한다.(방향전환2번)

이렇게 방향전환이 1번 혹은 2번 발생하면 목적지에 도달할 수 있지만 무한루프의 경우에는 방향전환이 계속 발생하게 된다.

따라서 방향전환이 3번발생하게되면 무한루프로 판단한다.

 

위의 내용은 틀렸습니다.

만약 총 50층으로 이루어져 있으며 현재 1층 목적지가 11층 위버튼 4 아래버튼 13이라면

방향전환이 3번이상으로 여러번 발생하게 됩니다.

위의 조건으로 코딩을 하게 되면 방향전환이 3번 발생했기 때문에 계단을 이용해야 합니다.

따라서 무한루프에 빠지는경우에 대해 더 고민해봐야 할 것 같습니다.

 

방문했던 층을 다시 방문하게 된다면? 이것이 무한루프입니다.

따라서 방문했던 층을 기록해 두었다가 방문했던 층에 도달하게 되면 이는 무한루프라고 판단할 수 있습니다.

또한 위 방법을 사용하게 되면 자연스럽게 계단을 이용해야 하는 경우 1번, 2번 또한 해결됩니다.

 

 

맞게 푼거같은데 뭔가 자꾸 틀리시는분들은

출발지가 목적지인 경우를 고려하셔야 합니다.

이 경우를 고려를 안해서 삽질을 많이 했습니다..

---

반례모음

50 1 11 4 13
11

10 1 1 1 1
0

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.StringTokenizer;

public class StartLink {
	static int buttonPressedCount = 0;
	static boolean useElevator = true;
	static HashSet<Integer> visited = new HashSet<Integer>();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int totalFloor = Integer.parseInt(st.nextToken());
		int currentLocation = Integer.parseInt(st.nextToken());
		int destination = Integer.parseInt(st.nextToken());
		int up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());

		visited.add(currentLocation);

		move(totalFloor, currentLocation, destination, up, down);

		if (useElevator) {
			bw.write(buttonPressedCount + "\n");
		} else {
			bw.write("use the stairs\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}

	static void move(int totalFloor, int currentLocation, int destination, int up, int down) {
		while (true) {
			// 출발지가 목적지인 경우도 고려해야 한다 따라서 맨 앞에 와야 함.
			if (currentLocation == destination) {
				break;
			}

			if (currentLocation + up > totalFloor && currentLocation - down < 1) {
				useElevator = false;
				break;
			}

			if (currentLocation < destination) {
				// have to go up
				if (currentLocation + up > totalFloor) {
					// 위로올라가야하는데 전체층수보다 큰 경우
					currentLocation -= down;
				} else {
					currentLocation += up;
				}

			} else {
				// have to go down
				if (currentLocation - down < 1) {
					// 아래로 내려가야하는데 1층보다 낮은 경우
					currentLocation += up;
				} else {
					currentLocation -= down;
				}

			}

			buttonPressedCount++;

			if (visited.contains(currentLocation)) {
				useElevator = false;
				break;
			} else {
				visited.add(currentLocation);
			}

		}
	}

}

코드설명

문제의 풀이들을 보면 많은분들이 BFS로 이 문제를 해결하였습니다.

 

우선 무한루프를 탐색하기 위해 방문했던 층을 다시 방문하는 경우를 무한루프를 판단하는 근거로 사용했다.

 

HashSet을 사용하여 방문했던층을 add하고 contains메소드를 사용하여 다시 방문하였는지 검사한다.

 

currentLocation이 목적지가 될때까지 또는 currentLocation에서 위, 아래로 움직일 수 없을때 까지 반복하며 현재 위치가 목적지보다 아래있으면 위버튼을 사용하고 현재 위치가 목적지보다 위에있으면 아래버튼을 사용하여 움직인다.

 

예외상황으로는 현재위치가 목적지보다 아래있어 위로 올라가야 하지만 위버튼을 누르게 되면 꼭대기층을 초과하는 경우에는 아래로 이동한 후 다시 위로 이동해야 한다.(아래로 가야하는 반대의 경우도 동일합니다.)