[BOJ] 5014 : 스타트링크
풀이
BFS
문제를 간단하게 보고 dfs방법으로 chk배열을 만들어서 중복못하게 한뒤에
조건을 만족하면 up으로 재귀, down으로 재귀 이런식으로 생각없이 짰다.
값이 도착층(G)에 가도 최소인지 확신할 수 없으므로 모든 경우를 탐색해야 한다.
따라서 시간초과를 받았다.
최솟값을 찾을 경우에는 BFS로 풀어야한다.
BFS로 하니까 바로 풀렸다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int chk[1000001];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//총 F층 사무실 G층 강호는 S층 ->엘베타고 S층에서 G층으로
//U는위로 U층, D는 아래로 D층 (두가지 층으로만 움직임, 해당없을경우 안움직임)
//최소 버튼 횟수
int f, s, g, u, d;
int ans = -1;
cin >> f >> s >> g >> u >> d;
chk[s] = 1;
queue<pair<int, int>> q;
q.push({ s, 0 });
while (!q.empty()) {
int x = q.front().first;
int cnt = q.front().second;
q.pop();
if (x == g) {
ans = cnt;
break;
}
int there = x + u;
if (there <= f&&chk[there] == 0) {
q.push({ there,cnt + 1 });
chk[there] = 1;
}
there = x - d;
if (there > 0 && chk[there] == 0) {
q.push({ there, cnt + 1 });
chk[there] = 1;
}
}
if (ans == -1)
cout << "use the stairs";
else
cout << ans;
return 0;
}
Written on March 30, 2019