[벡준] 5014 - 스타트링크 (자바/Java)

문제 링크

성능 요약

메모리: 93460 KB, 시간: 232 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

---

처음에는 무지성으로 bfs를 돌렸더니 메모리 초과가 났다

횟수를 셀 때 같은 시기(?)에 큐에 들어간 것들은 같은 cnt가 되어야 했기에 이걸 하나하나 지정하다보니 메모리가 초과된 것 같다.

다른 풀이를 참고하니.. 횟수를 셀 때는 큐의 사이즈만큼 반복문을 돌리면 된다는 것을 배웠다!! 나중에 써먹을 곳이 많을듯

그리고 방문여부를 확인해서 다시 방문이 되었다면 무한루프로 이어질 것이기 때문에 queue에 추가해주지 않으면 된다.

	static void bfs(int floor, int cnt) {
		Queue<Integer> q = new LinkedList<>();

		q.add(floor);

		while (!q.isEmpty()) {
			int size = q.size();
			while (size > 0) {
				size--;
				int tmp = q.poll();
				if (tmp == G) {
					ans = cnt;
					return;
				}

				if (tmp < 1 || tmp > F)
					continue;
				if (visited[tmp])
					continue;
				visited[tmp] = true;
				q.add(tmp + U);
				q.add(tmp - D);
			}

			cnt++;

		}

	}

메모리 초과가 난 후에 bfs를 활용하지 않고 수학적으로 구현하려고 했는데, 조건을 모두 충족시키도록 구현하는 게 어려운 것 같다.

내가 생각한 건 U와 D가 모두 짝수이고, 이동해야 할 층수가 홀수라면 불가능하다는 것과, U또는 D가 0일 때 이동해야할 층수의 부호에 따라 엘레베이터로 이동할 수 있는지의 여부가 달라진다는 것이었다.

이 외에도 여러 조건이 있을텐데 그걸 충족하지 못한 것 같다.

-- 틀린 풀이

// 0보다 크면 무조건 U를 해야되고
		int dis = G - floor;
		if (U % 2 == D % 2 && U % 2 == 0 && dis % 2 != 0) {
			return;
		}
		int cnt = 0;
		if (dis >= 0) {
			if (U == 0)
				return;

			cnt = dis / U;
			while (true) {
				if ((cnt * U - dis) % D == 0 && (cnt * U - dis) > 0) {
					ans = cnt + (cnt * U - dis) / D;
					return;
				} else
					cnt++;
			}
		} else {
			// 0보다 작으면 무조건 D를 해야됨
			if (D == 0)
				return;

			cnt = dis / D;
			while (true) {
				if ((cnt * D + dis) % U == 0 && (cnt * D + dis) > 0) {
					ans = cnt + (cnt * D + dis) / U;
					return;
				} else
					cnt++;
			}
		}

 

 

아무튼 bfs와 queue의 사이즈를 활용하니까 깔끔한 풀이가 되었다.

package Gold.g5;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_5014_스타트링크 {
	static int F, S, G, U, D;
	static int ans;
	static boolean visited[] = new boolean[1000001];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		F = sc.nextInt();
		S = sc.nextInt();
		G = sc.nextInt();
		U = sc.nextInt(); // +
		D = sc.nextInt(); // -
		ans = -1;
		bfs(S, 0);
		if (ans == -1)
			System.out.println("use the stairs");
		else
			System.out.println(ans);

	}

	static void bfs(int floor, int cnt) {
		Queue<Integer> q = new LinkedList<>();

		q.add(floor);

		while (!q.isEmpty()) {
			int size = q.size();
			while (size > 0) {
				size--;
				int tmp = q.poll();
				if (tmp == G) {
					ans = cnt;
					return;
				}

				if (tmp < 1 || tmp > F)
					continue;
				if (visited[tmp])
					continue;
				visited[tmp] = true;
				q.add(tmp + U);
				q.add(tmp - D);
			}

			cnt++;

		}

	}
}