[BOJ] 5014번 : 스타트링크

1. problem : 

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

 

 

2. solution 1: 

#include <bits/stdc++.h>
using namespace std;
int f, s, g, u, d; 
typedef long long ll;
long long elev[1000005]; // 몇번째에 도착했는지 기록 ; 
queue<int> Q; 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> f >> s >> g >> u >> d; 
	elev[s] = 1; 
	Q.push(s); 
	int dx[2] = { u,-d };
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 2; dir++) {
			int nx = cur + dx[dir]; 
			if (nx < 1 || nx > f || elev[nx]) continue;
			elev[nx] = elev[cur] + 1ll;
			Q.push(nx);
		}
		if (elev[g]) break;
	}
	if (!elev[g]) {
		cout << "use the stairs" << '\n'; 
		return 0;
	}
	cout << elev[g] - 1 << '\n';
}

bfs를 이용해 풀었다. 이때, 기존의 2차원 평면이 필요 없기에, 1차원 평면을 이용했다. 그에 따라, dx 축만 사용했다. 

 

3. solution 2 : 

// Authored by : std-freejia
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/8f34874217304e3ca3a499f672788d70
#include <bits/stdc++.h>
using namespace std;

int f, s, g, u, d;
int dist[1000002];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> f >> s >> g >> u >> d;
  fill(dist+1, dist+f+1, -1);
  
  queue<int> q;
  dist[s] = 0; // 현재 위치의 거리를 0으로 둠
  q.push(s); // s층에서 시작
  while(!q.empty()){
    int cur = q.front(); q.pop();
    for(auto nxt : {cur + u, cur - d}){
      if(nxt > f || nxt <= 0 || dist[nxt] != -1) continue;
      dist[nxt] = dist[cur] + 1;
      q.push(nxt);
    }
  }

  if(dist[g] == -1) cout << "use the stairs";
  else cout << dist[g];
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/5014.cpp

basic-algo-lecture/0x09/solutions/5014.cpp at master · encrypted-def/basic-algo-lecture

이 코드가 훨씬 빠르게 동작했다. 메모리 소비도 훨씬 줄었다. auto nx : {cur + u , cur - d}를 이용했다는 점과 long long을 int로 바꿨다는 점이 크게 작용했던 것 같다.