백준 16884번 [나이트 게임](C++) -yes6686- 티스토리

백준 문제 풀이: 16884 [나이트 게임]

---

문제 링크: https://www.acmicpc.net/problem/16884

문제 설명:

나이트 게임은 체스판에서 두 플레이어가 번갈아가며 나이트를 배치하는 게임입니다. 한 번 배치된 나이트는 특정 규칙에 따라 공격 가능한 위치를 점유하며, 배치할 수 없는 상태가 되면 패배합니다. 이 문제의 핵심은 점대칭 개념을 활용하여 최적의 게임 전략을 계산하는 것입니다.

점대칭 개념:

• 점대칭은 도형을 한 점을 중심으로 180° 회전했을 때 본래 도형과 일치하는 대칭입니다.
• 체스판의 크기가 짝수일 경우, 상대가 놓은 나이트의 점대칭 위치에 나이트를 배치하면 후공이 항상 유리합니다.
• 체스판의 크기가 홀수일 경우, 선공이 중앙 지점에 나이트를 배치하여 유리한 게임을 이끌어 갈 수 있습니다.

---

문제 해결 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt(); // 테스트 케이스 수
        while (T-- > 0) {
            int N = scanner.nextInt(); // 체스판 크기
            // 짝수면 후공이 이기고, 홀수면 선공이 이긴다.
            if (N % 2 == 0) {
                System.out.println("cubelover");
            } else {
                System.out.println("koosaga");
            }
        }
        scanner.close();
    }
}

예제 입력:

3
1
2
3

예제 출력:

koosaga
cubelover
koosaga

---

문제 설명 보충

이 문제는 점대칭 개념을 이해하면 간단히 해결할 수 있습니다:

• N이 짝수인 경우: 후공은 선공이 어디에 나이트를 놓든지 항상 점대칭 위치에 나이트를 놓아 상대의 공간을 모두 대칭으로 막을 수 있습니다. 따라서 후공이 승리합니다.
• N이 홀수인 경우: 선공은 중앙 지점에 나이트를 놓아 점대칭 위치가 없는 상태를 만듭니다. 이후 게임은 선공에게 유리하게 진행됩니다.

---

코드 설명

• 핵심 로직: 체스판의 크기 N을 기준으로 짝수인지 홀수인지 판단하여 승자를 출력합니다.
• 구현 세부사항:
  • N % 2 == 0: 후공이 승리 ("cubelover")
  • N % 2 == 1: 선공이 승리 ("koosaga")
• 시간 복잡도: 테스트 케이스 수를 T라 할 때, 각 테스트 케이스에 대해 O(1)의 시간이 소요되므로 전체 시간 복잡도는 O(T)입니다.

---

결과

이 코드는 주어진 체스판 크기 N에 대해 최적의 플레이를 했을 때 누가 승리하는지를 정확히 판단합니다. 게임 이론과 점대칭 개념을 이해하는 데 좋은 연습이 되는 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!