2026-02-26 문제풀이

나이트의 이동

풀이

일단 경로를 따라가봐야했다. 뭔가 규칙이 발견될 것이다. 손으로 쓰다가 규칙이 안보여서 포기하고 아래 코드를 짜서 확인해봤다.

노가다 코드

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlll;
#define xx first
#define yy second

const int MX = 30;

const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

ll cal(ll x, ll y){
    ll ry = MX + 1 - y;
    return (x + ry - 1) * (x + ry - 2) / 2 + ry;
}

int main(){
    fast_io
    vector<vector<int>> G(MX+1, vector<int>(MX+1, -1));
    queue<pii> q;
    q.push({1, MX});
    int idx = 1;
    while(!q.empty()){
        int x = q.front().xx;
        int y = q.front().yy;
        q.pop();
        G[y][x] = idx++;

        int mn = 1e9+1;
        int ry = -1, rx = -1;
        for(int i=0;i<8;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny > 0 && ny <= MX && nx > 0 && nx <= MX && G[ny][nx] == -1){
                if(mn > cal(nx, ny)){
                    mn = cal(nx, ny);
                    ry = ny;
                    rx = nx;
                }
            }
        }
        if(ry != -1){
            q.push({rx, ry});
        }
    }


    for(int i=1;i<=MX;i++){
        for(int j=1;j<=MX;j++){
            cout << G[i][j] << ' ';
        }
        cout << '\n';
    }
}

노가다 결과(대충)

25 34 29 56 87 102 117 90 105 120 151 166 181 148 223 186 
28 31 26 35 46 71 84 101 116 91 106 121 134 113 182 147 224 
33 24 13 30 55 86 47 72 83 100 115 92 107 122 133 136 183 
12 27 32 23 36 45 54 85 48 73 82 99 114 135 112 123 132 137 
3 6 9 14 17 20 39 44 53 42 51 76 93 108 79 96 111 126 145 
8 11 2 5 22 37 16 19 40 49 74 81 98 77 94 109 124 131 138 
1 4 7 10 15 18 21 38 43 52 41 50 75 80 97 78 95 110 125 130 

위 텍스트는 이동하는 순서를 나타낸 것이다.

처음에는 뭔가 일자로 쭉 이동할 것 같았지만 생각보다 모든 칸을 잘 채우면서 이동한다. 채울 때는 크게 보면 왼쪽 모서리부터 쭉 채우는 느낌이다. (숫자 크기대로)

아 그런데 아직도 모르겠네 ㅠㅠ 규칙이 뭐이리 어려워

항상 느끼는건데 나이트의 이동은 진짜 너무 어렵다 ㅠ

일단 숫자가 작은 것은 $x+y=k$ 그래프를 평행이동 하면서 볼 수 있으니깐 이동할 수 있는 후보중에서 $x+y$ 가 작은 순서대로 방문하고 x+y가 같으면 y가 작은 순으로 방문한다.

근데 중요한 사실을 알아냈다. MX를 100으로 두고 해봤는데 $100\times 100 = 10000$ 개 중에서 굉장히 많은 부분이 -1(비워져있음)이었다는 것이다.

그래서 최댓값을 추적해보니 MX가 100, 1000이던간에 2402로 나왔다. 그러니까 2402까지 가면 모두 방문했었어서 고립되고 이동할 수 없는 상황이 나온다는 것이다…. 이건 상상도 못했다.. ㅋㅋ

따라서 노가다로 구해두고 출력하면 된다.

코드

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlll;
#define xx first
#define yy second

const int MX = 100;

const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

ll cal(ll x, ll y){
    ll ry = MX + 1 - y;
    return (x + ry - 1) * (x + ry - 2) / 2 + ry;
}

int main(){
    fast_io
    int k; cin >> k;
    vector<vector<int>> G(MX+1, vector<int>(MX+1, -1));
    queue<pii> q;
    q.push({1, MX});
    int idx = 1;
    vector<int> res(3000, 0);
    while(!q.empty()){
        int x = q.front().xx;
        int y = q.front().yy;
        q.pop();
        G[y][x] = idx;
        res[idx-1] = cal(x, y);
        idx += 1;

        int mn = 1e9+1;
        int ry = -1, rx = -1;
        for(int i=0;i<8;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny > 0 && ny <= MX && nx > 0 && nx <= MX && G[ny][nx] == -1){
                if(mn > cal(nx, ny)){
                    mn = cal(nx, ny);
                    ry = ny;
                    rx = nx;
                }
            }
        }
        if(ry != -1){
            q.push({rx, ry});
        }
    }

    cout << res[k];
}

마무리

솔직히 놀랐다. ㅋㅋ 좀 재밌는 문제인듯?