룩, 비숍, 킹, 나이트, 궁전 게임 문제(백준 16880번) 풀이

작성일 | In , |

맞았습니다

룩, 비숍, 킹, 나이트, 궁전 게임

chess

백준 링크

체스판 위에 체스말 $N$개가 놓여져 있다. 가장 왼쪽 아랫칸 좌표는 $(0, 0)$이고 가장 오른쪽 윗칸의 좌표는$(10^9-1 * 10^9 -1)$이다. 두 개 이상의 말이 한 칸에 동시에 있을 수 있다.

체스말의 좌표가 $(x, y)$일때 다음과 같이 움직일 수 있다.

  • 룩,R
    • $(x, i) (0 \leq i<y)$
    • $(i, y) (0 \leq i<x)$
  • 비숍,B
    • $(x-i, y-i) (0<i\leq min(x,y))$
  • 킹,K
    • $(x, y-1)(y>0)$
    • $(x-1, y)(x>0)$
    • $(x-1, y-1)(x>0,y>0)$
  • 나이트,N:
    • $(x-1, y-2)(x>0, y>1)$
    • $(x-2, y-1)(x>1, y>0)$
  • 궁전,P:
    • $(x, i) (0 \leq i<y)$
    • $(i, y) (0 \leq i<x)$
    • $(x-1, y-1)(x>1,y>1)$

구사가와 큐브러버가 턴을 번갈아면서 체스말 한 개를 움직일 때 더이상 체스말을 이동시킬수없는 사람이 게임을 지게 된다. 최선의 전략으로 게임을 할 때 게임에서 이기는 사람의 이름을 출력하시오.

풀이

solved.ac 기준 다이아 5 레벨 문제다 보니 어느정도 사전 지식이 필요하다. 스프라그-그런디 정리를 알고 있지 않으면 먼저 그것을 공부하는 것을 추천한다.

좌표의 범위가 넓기 때문에 전처리로 그런디 넘버를를 계산하면서 각각 말의 패턴을 다 구한 후 xor을 해서 답을 구할 수 있다.

이제 각각의 말마다 그런디 넘버를 계산하면서 패턴을 찾아보자.

비숍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int m = 10;
int d[m][m];
int main() {
    d[0][0] = 0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            if (i == 0 && j == 0) continue;
            unordered_set<int> s;
            for (int k=0; k<min(i,j); k++) {
                s.insert(d[k][j]);
            }
            for (int k=0;; k++) {
                if (s.count(k) == 0) {
                    d[i][j] = k;
                    break;
                }
            }
        }
    }

    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}

1
2
3
4
5
6
7
8
9
10
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 2 2 2 2 2 2 2 2
0 1 2 3 3 3 3 3 3 3
0 1 2 3 4 4 4 4 4 4
0 1 2 3 4 5 5 5 5 5
0 1 2 3 4 5 6 6 6 6
0 1 2 3 4 5 6 7 7 7
0 1 2 3 4 5 6 7 8 8
0 1 2 3 4 5 6 7 8 9

그러므로 코드는 다음과 같다.

1
2
3
int bishop(int x, int y) {
    return min(x, y);
}

사실 굳이 코드를 안짜도 이 정도는 쉬워서 알수 있긴 하다.

킹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int m = 20;
int d[m][m];
int main() {
    d[0][0] = 0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            if (i == 0 && j == 0) continue;
            unordered_set<int> s;
            if (i>0) s.insert(d[i-1][j]);
            if (j>0) s.insert(d[i][j-1]);
            if (i>0 && j>0) s.insert(d[i-1][j-1]);
            for (int k=0;; k++) {
                if (s.count(k) == 0) {
                    d[i][j] = k;
                    break;
                }
            }
        }
    }

    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}

1
2
3
4
5
6
7
8
9
10
0 1 0 1 0 1 0 1 0 1
1 2 3 2 3 2 3 2 3 2
0 3 0 1 0 1 0 1 0 1
1 2 1 2 3 2 3 2 3 2
0 3 0 3 0 1 0 1 0 1
1 2 1 2 1 2 3 2 3 2
0 3 0 3 0 3 0 1 0 1
1 2 1 2 1 2 1 2 3 2
0 3 0 3 0 3 0 3 0 1
1 2 1 2 1 2 1 2 1 2

패턴이 보일락 말락한다.

좀더 확실하게 $20 * 20$을 보도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2
0 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 2 1 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2
0 3 0 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 2 1 2 1 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2
0 3 0 3 0 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 2 1 2 1 2 1 2 3 2 3 2 3 2 3 2 3 2 3 2
0 3 0 3 0 3 0 3 0 1 0 1 0 1 0 1 0 1 0 1
1 2 1 2 1 2 1 2 1 2 3 2 3 2 3 2 3 2 3 2
0 3 0 3 0 3 0 3 0 3 0 1 0 1 0 1 0 1 0 1
1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 2 3 2 3 2
0 3 0 3 0 3 0 3 0 3 0 3 0 1 0 1 0 1 0 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 2 3 2
0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 1 0 1 0 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 2
0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 1 0 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2
0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

$0$ 패턴

zero

$x$ 가 짝수면서 $y$가 짝수

$2$ 패턴

two

$x$ 가 홀수면서 $y$가 홀수

$1$ 패턴

one

$0, 2$가 아니면서 $min(x, y)$가 짝수

$3$ 패턴

$0, 1, 2$가 아닌 나머지

요약

1
2
3
4
5
6
int king(int x, int y) {
    if (x%2==0 && y%2==0) return 0;
    if (x%2 && y%2) return 2;
    if (min(x,y)%2==0) return 1;
    return 3;
}

나이트

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int m = 10;
int d[m][m];

int main() {
    d[0][0] = 0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            if (i == 0 && j == 0) continue;
            unordered_set<int> s;
            if (i>0 && j>1) s.insert(d[i-1][j-2]);
            if (j>0 && i>1) s.insert(d[i-2][j-1]);
            for (int k=0;; k++) {
                if (s.count(k) == 0) {
                    d[i][j] = k;
                    break;
                }
            }
        }
    }

    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}

1
2
3
4
5
6
7
8
9
10
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1
0 1 1 1 2 2 2 2 2 2
0 1 1 0 0 0 0 0 0 0
0 1 2 0 0 1 1 1 1 1
0 1 2 0 1 1 1 2 2 2
0 1 2 0 1 1 0 0 0 0
0 1 2 0 1 2 0 0 1 1
0 1 2 0 1 2 0 1 1 1
0 1 2 0 1 2 0 1 1 0

패턴을 알아 차릴수 있겠는가? 정리하면 다음과 같다.

1
2
3
4
5
6
int knight(int x, int y) {
    if (min(x,y)%3 == 0) return 0;
    if (min(x,y)%3 == 1 && x == y)  return 0;
    if (min(x,y)%3 == 2 && abs(x-y) > 1) return 2;
    return 1;
}

룩

좀 어렵다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const int m = 10;
int d[m][m];

int main() {
    d[0][0] = 0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            if (i == 0 && j == 0) continue;
            unordered_set<int> s;
            for (int k=0; k<i; k++) {
                s.insert(d[k][j]);
            }
            for (int k=0; k<j; k++) {
                s.insert(d[i][k]);
            }
            for (int k=0;; k++) {
                if (s.count(k) == 0) {
                    d[i][j] = k;
                    break;
                }
            }
        }
    }

    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}

1
2
3
4
5
6
7
8
9
10
 0  1  2  3  4  5  6  7  8  9
 1  0  3  2  5  4  7  6  9  8
 2  3  0  1  6  7  4  5 10 11
 3  2  1  0  7  6  5  4 11 10
 4  5  6  7  0  1  2  3 12 13
 5  4  7  6  1  0  3  2 13 12
 6  7  4  5  2  3  0  1 14 15
 7  6  5  4  3  2  1  0 15 14
 8  9 10 11 12 13 14 15  0  1
 9  8 11 10 13 12 15 14  1  0

이 숫자 패턴이 뭔지 알겠는가? 수학적 센스가 뛰어난 사람은 금방 알아 맞출수 있다. 나는 그렇지 않았기 때문에 오래걸렸다…

답은 허무하고 간단하다.

1
2
3
int rook(int x, int y) {
    return x^y;
}

궁전

이 문제가 어려운 이유, 이문제만 따로 16879 궁전게임으로 존재하며 플레티넘 1이다. 미리 그런디 넘버를 계산하고 패턴을 파악해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int m = 10;
int d[m][m];
int main() {
    d[0][0] = 0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            if (i == 0 && j == 0) continue;
            unordered_set<int> s;
            for (int k=0; k<i; k++) {
                s.insert(d[k][j]);
            }
            for (int k=0; k<j; k++) {
                s.insert(d[i][k]);
            }
            if (i-1 >= 0 && j-1 >= 0) {
                s.insert(d[i-1][j-1]);
            }
            for (int k=0;; k++) {
                if (s.count(k) == 0) {
                    d[i][j] = k;
                    break;
                }
            }
        }
    }

    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}

1
2
3
4
5
6
7
8
9
10
 0  1  2  3  4  5  6  7  8  9
 1  2  0  4  5  3  7  8  6 10
 2  0  1  5  3  4  8  6  7 11
 3  4  5  0  1  2  9 10 11  6
 4  5  3  1  2  0 10 11  9  7
 5  3  4  2  0  1 11  9 10  8
 6  7  8  9 10 11  0  1  2  3
 7  8  6 10 11  9  1  2  0  4
 8  6  7 11  9 10  2  0  1  5
 9 10 11  6  7  8  3  4  5  0

자세히 보면 3*3 단위로 마치 스도쿠 배열처럼 특정 패턴이 반복된다는 것을 관찰할 수 있다.

그리고 그 3*3안에서도 패턴들이 있는데 이를 정리하면 다음과 같다. (이미 푼 문제라서 쉽게 넘어갔으나 찾기 좀 어렵다)

1
2
3
int palace(int x, int y) {
    return (x+y)%3 + ((x/3)^(y/3))*3;
}

소스코드

위 5가지 패턴을 합치기만 하면 된다. 소스코드는 짧고 명쾌하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int palace(int x, int y) {
    return (x+y)%3 + ((x/3)^(y/3))*3;
}
inline int rook(int x, int y) {
    return x^y;
}
inline int knight(int x, int y) {
    if (min(x,y)%3 == 0) return 0;
    if (min(x,y)%3 == 1 && x == y)  return 0;
    if (min(x,y)%3 == 2 && abs(x-y) > 1) return 2;
    return 1;
}
inline int bishop(int x, int y) {
    return min(x, y);
}
inline int king(int x, int y) {
    if (x%2==0 && y%2==0) return 0;
    if (x%2 && y%2) return 2;
    if (min(x,y)%2==0) return 1;
    return 3;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, ans = 0; cin >> N;
    while (N--) {
        int x, y; cin >>x >> y;
        char c; cin >> c;
        if (c == 'B') ans^=bishop(x,y);
        if (c == 'N') ans^=knight(x,y);
        if (c == 'K') ans^=king(x,y);
        if (c == 'R') ans^=rook(x,y);
        if (c == 'P') ans^=palace(x,y);
    }
    if (ans) cout << "koosaga\n";
    else cout << "cubelover\n";
}

맞았습니다!

순위

532바이트만에 짠 kyo20111님의 풀이는 같은 내용이지만 정말 숏코딩을 잘하셨다!

물론 이문제 숏코딩 1등은 역시나 sait2000님이시긴 한다. :god: