[BOJ] 17071 : 숨바꼭질 5
풀이
BFS
2019라인플러스 상반기 인턴 채용 5문제중에 마지막 문제 변형문제다.
이문제만 못풀었었다. n이 50만으로 상당히 크다. 게다가 이문제에서 시간제한은 0.25초이다.
(시간제한이 이렇게 되면 NlogN으로도 시간초과가 뜰수있다 (500000 * log(2)500000은 대략 천만))
문제해결에는 djm03178 님의 아이디어가 큰 몫을 했다.
어떤 점 x에 t초에 도달할 수 있다면, t+2, t+4, t+6, … 에도 x에 도달할 수 있다.
좌우로 한 번 왔다갔다하면 다시 제자리로 돌아오기 때문이다.
즉, 짝수초에 x에 도달하는 최단 과 홀수초에 x에 도달하는 최단거리를 각각 구하면 된다는 것이 포인트이다.
chk배열을 홀수,짝수를 따로 만든 후
BFS로 cnt가 홀수인지 짝수인지에 따라서 chk판정을 했다.(chk에는 최소거리를 넣어줬다)
이렇게 되면 시간복잡도는 최대 백만이다.
그후 k가 1초에 1, 2초에 2..이렇게 이동하니까
500000까지 이동하도록 하면서
*** chk가 cnt보다 작고, chk에서 +2,+4,+6…을 해서 cnt를 만들 수 있는지를 확인했다.
( (cnt-chk[k])%2==0 인지 확인했다. )
계속 88%에서 틀렸다고 나오는 문제가 있었는데,
처음 배열 초기화를 -1로 해서 해결했다.
0초가 존재할 수 있는 경우라면 -1로 초기화를 하는게 안전하다는 것을 깨달았다.
코드
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
//좌표에 도달할 수 있는 가장 빠른시간
int oddchk[500001];
int evenchk[500001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k;
cin >> n >> k;
if (n == k) {
cout << 0 << '\n';
return 0;
}
memset(oddchk, -1, sizeof(oddchk));
memset(evenchk, -1, sizeof(evenchk));
int ans = -1;
queue<pair<int,int>> q;
q.push({ n,0 });
evenchk[n] = 0;
while (!q.empty()) {
int x = q.front().first;
int cnt = q.front().second;
q.pop();
if (cnt % 2 == 0) {
if (x + 1 <= 500000 && evenchk[x + 1] == -1) {
q.push({x+1,cnt+1});
evenchk[x + 1] = cnt+1;
}
if (x - 1 >= 0 && evenchk[x - 1] == -1) {
q.push({ x - 1,cnt + 1 });
evenchk[x - 1] = cnt + 1;
}
if (x * 2 <= 500000 && evenchk[x * 2] == -1) {
q.push({ x * 2,cnt + 1 });
evenchk[x * 2] = cnt + 1;
}
}
else if (cnt % 2 == 1) {
if (x + 1 <= 500000 && oddchk[x + 1] == -1) {
q.push({ x + 1,cnt + 1 });
oddchk[x + 1] = cnt + 1;
}
if (x - 1 >= 0 && oddchk[x - 1] == -1) {
q.push({ x - 1,cnt + 1 });
oddchk[x - 1] = cnt + 1;
}
if (x * 2 <= 500000 && oddchk[x * 2] == -1) {
q.push({ x * 2,cnt + 1 });
oddchk[x * 2] = cnt + 1;
}
}
}
int i = k+1;
int cnt = 1;
while (i<=500000) {
if (oddchk[i]!= -1 && oddchk[i] <= cnt) {
if ((cnt - oddchk[i]) % 2 == 0) {
if (ans == -1 || ans > cnt) {
ans = cnt;
}
}
}
if (evenchk[i] != -1 && evenchk[i] <= cnt) {
if ((cnt - evenchk[i]) % 2 == 0) {
if (ans == -1 || ans > cnt) {
ans = cnt;
}
}
}
cnt++;
i += cnt;
}
cout << ans;
return 0;
}
Written on April 9, 2019