[BOJ] 1697 : 숨바꼭질

문제 링크

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

실버라고 만만하게 봤다

풀이

BFS를 활용한 문제. 앞으로 한 칸을 가든 뒤로 한 칸을 가든 순간이동을 하든 사용되는 시간은 동일하다.

큐를 만들어서 위치와 시간을 저장하려고 했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N, K;
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    queue<pair<int, int>> q;
    q.push({ N, 0 });
 
    while (!q.empty()) {
        int now = q.front().first;
        int Time = q.front().second;
        q.pop();
        if (now == K) {
            cout << Time << "\n";
            break;
        }
        q.push({ now * 2, Time + 1 });
        q.push({ now + 1, Time + 1 });
        q.push({ now - 1, Time + 1 });
    }
    return 0;
}
 
 

말 그대로 BFS에 기초한 코드다. 그랬더니 메모리 초과를 마주했다. 시간초과는 자주 받았어도 메모리 초과는 처음인 것 같다.

아마 한 번 돌때마다 큐에 3개씩 밀어넣어서 그런 것같다. 무조건 밀어 넣는게 아니라 예외를 걸어줘야 할 것 같다.

Time_mem 이라는 배열을 만들어서 그 위치까지 가는데 걸린 시간을 저장했다. 만약 같은 위치에 도달했을 때 걸린 시간이 이미 저장된 시간보다 크다면 굳이 큐에 다음 경우를 밀어넣을 필요가 없다. 그 경우 그냥 큐에 더 넣지않고 continue로 넘어갔다.

이렇게 했더니 큐는 줄일 수 있었지만 문제가 하나 더 있었다. now * 2 를 계속 하다보니 now가 무한히 커질 수 있었다.

그렇게 되면 Time_mem의 범위를 K의 범위로 지정해놨는데 오버플로우가 나게된다. 또 시간낭비에 메모리 낭비다.

now의 2배가 K의 2배를 넘을 수 없다고 판단했다. 왜냐 now의 2배가 K의 2배보다 크거나 같다는 건 그 전에 이미 도달할 수 있었다는 뜻이다. 그래서 그 경우 예외를 걸어줬다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N, K;
int Time_mem[1000000 + 5];
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    memset(Time_mem, -1, sizeof(Time_mem));
    queue<pair<int, int>> q;
    q.push({ N, 0 });
    while (!q.empty()) {
        int now = q.front().first;
        int Time = q.front().second;
        q.pop();
        if (now == K) {
            cout << Time << "\n";
            break;
        }
        if (Time_mem[now] != -1 && Time_mem[now] <= Time)
            continue;
        Time_mem[now] = Time;
        q.push({ now + 1, Time + 1 });
        q.push({ now - 1, Time + 1 });
        if (now * 2 >= K * 2)
            continue;
        q.push({ now * 2, Time + 1 });
    }
    return 0;
}