4112. 이상한 피라미드 탐험

4112. 이상한 피라미드 탐험

BFS 문제였기 때문에, 각 노드간에 이동할 수 있는지 여부만 추려내면 되는 문제였다.

근데 나는 딱히 방법이 떠오르지 않아서 약간 노가다 식으로 진행했다.

일단 1인경우, 맨 왼쪽 대각선인 경우, 맨 오른쪽 대각선이 경우, 그외 이렇게 나누어서 문제를 풀었다.

중복계산을 피하기 위해 tc안에 들어가기 전에,

각 숫자들을 for문으로 돌면서 해당하는 라인과 왼쪽인지 오른쪽인지를 판단하도록 했다.

이때 1은 왼쪽,오른쪽 둘다 걸쳐 있다고 체크를 해줬다.

그리고 BFS를 돌면서, 다음 정점을 찾을 때는 1인지,왼쪽대각선인지,오른쪽대각선인지, 그 외 경우인지 나누어서 함수를 진행했다. 

그리고 사실 이동할 때 1이상 1만이하인지를 체크해줘야 하는데 귀찮아서 배열을 아주 크게 만들어서 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef struct {
    bool left = false;
    bool right = false;
    int line = 0;
}n;
int dist[20001];
bool check[20001];
n num[20001];
 
void init()
{
    for (int i = 0; i < 10001; i++)
    {
        dist[i] = 0;
        check[i] = false;
    }
}
 
void chk_left(int x, queue<int> &q)
{
    int L = num[x].line;
    if (!check[x + 1 - L])
    {
        check[x + 1 - L] = true;
        q.push(x + 1 - L);
        dist[x + 1 - L] = dist[x] + 1;
    }
    if (!check[x + 1])
    {
        check[x + 1] = true;
        q.push(x + 1);
        dist[x + 1] = dist[x] + 1;
    }
    if (!check[x + 1 + L])
    {
        check[x + 1 + L] = true;
        q.push(x + 1 + L);
        dist[x + 1 + L] = dist[x] + 1;
    }
    if (!check[x + L])
    {
        check[x + L] = true;
        q.push(x +L);
        dist[x +L] = dist[x] + 1;
    }
 
}
 
void chk_right(int x, queue<int> &q)
{
    int L = num[x].line;
    if (!check[x - L])
    {
        check[x - L] = true;
        q.push(x - L);
        dist[x - L] = dist[x] + 1;
    }
    if (!check[x - 1])
    {
        check[x - 1] = true;
        q.push(x - 1);
        dist[x - 1] = dist[x] + 1;
    }
    if (!check[x  + L])
    {
        check[x  + L] = true;
        q.push(x  + L);
        dist[x  + L] = dist[x] + 1;
    }
    if (!check[x + 1 + L])
    {
        check[x + L+1] = true;
        q.push(x + L+1);
        dist[x + L+1] = dist[x] + 1;
    }
}
void chk(int x, queue<int> &q)
{
    int L = num[x].line;
    if (!check[x - L])
    {
        check[x - L] = true;
        q.push(x - L);
        dist[x - L] = dist[x] + 1;
    }
    if (!check[x - L + 1])
    {
        check[x - L+1] = true;
        q.push(x - L+1);
        dist[x - L+1] = dist[x] + 1;
    }
    if (!check[x - 1])
    {
        check[x - 1] = true;
        q.push(x - 1);
        dist[x - 1] = dist[x] + 1;
    }
    if (!check[x + 1])
    {
        check[x +1] = true;
        q.push(x + 1);
        dist[x +1] = dist[x] + 1;
    }
    if (!check[x + L])
    {
        check[x + L] = true;
        q.push(x + L);
        dist[x + L] = dist[x] + 1;
    }
    if (!check[x + L + 1])
    {
        check[x + L+1] = true;
        q.push(x + L+1);
        dist[x + L+1] = dist[x] + 1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
 
    int sum = 1;
    for (int i = 1; sum <= 10000; i++)
    {
        num[sum].left = true;
        sum += i;
    }
    sum = 1;
    for (int i = 2; sum <= 10000; i++)
    {
        num[sum].right = true;
        sum += i;
    }
    sum = 1;
    for (int i = 1; sum <= 10000; i++)
    {
        for (int j = sum; j < sum + i; j++)
        {
            num[j].line = i;
        }
        sum += i;
    }
 
    for (int t = 1; t <= tc; t++)
    {
        init();
        int a, b;
        cin >> a >> b;
        init();
        queue<int> q;
        q.push(a);
 
        while (!q.empty())
        {
            int now = q.front();
            q.pop();
 
            if (now == b)
            {
                break;
            }
 
            if (num[now].left && num[now].right)
            {
                if (!check[2])
                {
                    check[2] = true;
                    q.push(2);
                    dist[2] = dist[now] + 1;
                }
                if (!check[3])
                {
                    check[3] = true;
                    q.push(3);
                    dist[3] = dist[now] + 1;
                }
                continue;
            }
 
            if (num[now].left && !num[now].right)
            {
                chk_left(now, q);
                continue;
            }
 
            if (!num[now].left && num[now].right)
            {
                chk_right(now, q);
                continue;
            }
 
            chk(now, q);
            continue;
        }
 
        cout << "#" << t << " " << dist[b] << "\n";
 
    }
    return 0;
}