백준 5014번 스타트링크

문제 이해

총 F층으로 이루어진 건물의 G층에 스타트링크가 위치한다.

강호는 현재 S층에서 G층으로 이동하려 한다.

엘리베이터는 위로 U층 올라가는 버튼, 아래로 D층 내려가는 버튼 두 가지다.

 

강호가 G층에 도착하기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다.

만약 엘리베이터로 G층까지 이동할 수 없다면 "use the stairs"를 출력한다.

 

풀이 설명

step이라는 배열을 두고, step[s]부터 시작해서 위, 아래로 이동하며 step[n]에 n층까지 이동하는 데 눌러야 할 최소 버튼 수를 저장하는 방법을 사용했다. 해결 방법은 다음과 같다.

 

1. F의 최댓값인 1,000,000 + 1 크기로 step 배열을 두고, -1로 초기화한다.

 

2. step[S]에 0을 저장하고 (S는 강호가 이동을 시작하는 층), 큐에 S를 넣는다.

 

3. 큐가 모두 비거나, G층에 도착할 때까지 반복하며 step[cur + U],  step[cur - D]에 step[cur] + 1 값을 저장해 준다.

cur은 큐의 가장 앞에 있는 값으로 현재 층이고, cur + U 와 cur - D는 각각 현재 층에서 U만큼 올라간, D만큼 내려간 층이다. 이 때, step[cur + U]나 step[cur - D]에 방문하지 않은 경우만 step값을 저장하고, 큐에 cur + U 또는 cur - D를 넣어준다.

 

4. 위의 탐색 결과로 step[G]가 -1이라면 G층을 방문하지 않은 상태이므로 "use the stairs"를 출력하고, 그렇지 않다면 step[G]를 출력해준다.

 

구현

// 5014번 스타트링크

#include <iostream>
#include <queue>
using namespace std;

#define MAX 1000000 + 1

int F, S, G, U, D;
int step[MAX];

queue<int> q;

int solution() {
	q.push(S);
	step[S] = 0;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		
		if (cur == G) break;

		if (cur + U <= F && step[cur + U] == -1) {
			step[cur + U] = step[cur] + 1;
			q.push(cur + U);
		}
		if (cur - D > 0 && step[cur - D] == -1) {
			step[cur - D] = step[cur] + 1;
			q.push(cur - D);
		}
	}

	return step[G];
}

void init() {
	for (int i = 0; i <= F; i++) {
		step[i] = -1;
	}
}

int main() {
	cin >> F >> S >> G >> U >> D;
	init();

	int ans = solution();
	if (ans == -1) cout << "use the stairs";
	else cout << ans;

	return 0;
}

 

오류가 있었던 부분

step 배열을 -1이 아닌 0으로 초기화해 값이 0이면 방문하지 않았다고 판단했었다. 

이 방법은 위의 코드에서는 U가 0일 때 문제가 생긴다.

 

예를 들어 강호가 10층에서 출발하고, 9층에 있는 스타트링크 사무실로 이동하려 하고, U는 0, D는 1이라고 하자.

 

solution함수의 반복문 안에서 층 방문 여부를 확인하고 step에 값을 저장해주는 부분에서 cur + U를 방문했는지 먼저 확인하게 된다. 여기서 U가 0이기 때문에 cur + U는 10 + 0으로 결국 출발 층인 10층이 되고, 10층은 방문했는데도 방문하지 않았다고 판단하여 step[10]에 step[cur], 즉, step[10] = 0에 1을 더한 1이 저장된다.

 

그리고 cur - D를 방문했는지 확인한다. cur - D = 10 - 1로 9층인데, 9층은 방문하지 않았으므로 step[9]에 step[10]에 1을 더한 2가 저장된다. 

 

10층에서 9층으로 이동하는 데 버튼은 1번만 누르면 되지만, 2번이라는 결과를 내게 되는 것이다. 

 

이는 step을 -1로 초기화하여 step의 값이 -1이면 방문하지 않았다고 판단하고, 처음에 step[S]에는 0을 저장해 줌으로써 해결하였다.

 

문제 링크: www.acmicpc.net/problem/5014