[C/C++] 숫자 퍼즐 게임 구현

#include <iostream>
#include <time.h>
#include <cmath>
 
// console input output 헤더파일
// 콘솔창에서 입출력하는 기능들을 제공하는 헤더파일이다.
#include <conio.h>
 
int main() {
    srand((unsigned int)time(NULL));
    int number[25];
    int idx1, idx2, tmp;
 
    // 배열의 맨 마지막 값을 공백으로 처리한다.
    for (int i = 0; i < 24; ++i) {
        number[i] = i + 1;
    }
    number[24] = INT_MAX;
 
    int currStarIdx = 24;
    bool isClear;
    int inversion = 0;
 
    // Parity Error에 의해서 절대 풀 수 없는 퍼즐이 나올 수 있음
    // 그런 경우 퍼즐을 다시 생성함.
    while (true) {
        for (int i = 0; i < 100; ++i) {
            idx1 = rand() % 24;
            idx2 = rand() % 24;
 
            tmp = number[idx1];
            number[idx1] = number[idx2];
            number[idx2] = tmp;
        }
 
        for (int i = 0; i < 22; ++i) {
            for (int j = i; j < 23; ++j) {
                if (number[i] > number[j])        ++inversion;
            }
        }
 
        if (sizeof(number) / sizeof(number[0]) % 2 == 0) {
            if (inversion % 2 != 0)        break;
        }
 
        else {
            if (inversion % 2 == 0)        break;
        }
    }
 
 
    while (true) {
        system("cls");
        // 1차원 배열을 2차원 배열처럼 처리할 수 있도록 한 것임.
        // 줄번호 * 가로개수 * 칸번호
        // 이런 공식이 2D 평면에서 무언가를 구해낼 때 많이 사용됨
        // 알아두면 나중에 유용함.
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; j++) {
                if (number[i * 5 + j] == INT_MAX)        std::cout << "*\t";
                else    std::cout << number[i * 5 + j] << "\t";
            }
            std::cout << std::endl;
        }
 
        isClear = true;
        for (int i = 0; i < 24; ++i) {
            if (number[i] != i + 1) {
                isClear = false;
                break;
            }
        }
 
        if (isClear) {
            std::cout << std::endl << "클리어 하였습니다!" << std::endl;
            break;
        }
 
        std::cout << "w : 위 s : 아래 a : 왼쪽 d : 오른쪽 q : 종료" << std::endl;
 
        // 플레이어가 w, a 등 문자만 입력하면 자동으로 동작하기를 원한다.
        // cin을 이용할 경우 문자 입력 후 Enter를 쳐야지 입력이 완료된다.
        // _getch() 함수는 문자 1개를 입력받는 함수로, Enter를 치지 않아도 문자를 누르는 순간
        // 바로 그 문자를 반환하고 종료된다.
        char playerInput = _getch();
 
        if (playerInput == 'q' || playerInput == 'Q')        break;
 
        switch (playerInput) {
        case 'w':
        case'W':
            if (currStarIdx > 4) {
                number[currStarIdx] = number[currStarIdx - 5];
                number[currStarIdx - 5] = INT_MAX;
                currStarIdx -= 5;
            }
            break;
        case 's':
        case'S':
            if (currStarIdx < 20) {
                number[currStarIdx] = number[currStarIdx + 5];
                number[currStarIdx + 5] = INT_MAX;
                currStarIdx += 5;
            }
            break;
        case 'a':
        case'A':
            if (currStarIdx % 5 != 0) {
                number[currStarIdx] = number[currStarIdx - 1];
                number[currStarIdx - 1] = INT_MAX;
                currStarIdx -= 1;
            }
            break;
        case 'd':
        case'D':
            if (currStarIdx % 5 != 4) {
                number[currStarIdx] = number[currStarIdx + 1];
                number[currStarIdx + 1] = INT_MAX;
                currStarIdx += 1;
            }
            break;
        default:
            break;
        }
    }
 
    std::cout << std::endl << "게임을 종료합니다." << std::endl;
 
 
    return 0;
}

 

5x5 숫자 퍼즐 게임을 구현한 전체 코드입니다.

1 ~ 24까지 숫자를 순서대로 나열하면 게임이 클리어되어 종료됩니다.

 

 

11 번째 라인에서 1 ~ 24 까지의 숫자와 공백 한 칸을 저장할 배열 number[25]를 선언합니다.

18 번째 라인은 number 배열의 마지막 원소를 공백으로 남겨놓기 위해 INT_MAX값을 저장한 것입니다.

밑의 과정은 로또 구현에서 배웠던 셔플 알고리즘입니다.

- 참고 링크 : [C/C++] 로또 구현 (tistory.com)

 

20 ~ 21번째 라인은 현재 공백의 위치를 저장할 변수, isClear의 경우 클리어 유무를 체크할 변수입니다.

22 번째 라인부터는 클리어 가능한 퍼즐 게임을 구현하기 위해 작성한 코드입니다. 아래에서 자세히 설명하겠습니다.

 

 

코드 설명에 앞서 퍼즐 게임의 구현에 대해 잠시 설명하겠습니다.

임의의 숫자 퍼즐 게임을 구현할 경우 클리어가 불가능한 경우가 많습니다. 이러한 현상을 Parity Error 라고 정의되어 있습니다. 저희의 경우 자세한 원인보단 완벽한 게임을 위해 이런 현상을 예방하는 방법만을 살펴보도록 합시다.

퍼즐의 숫자가 아래와 같다고 가정해 봅시다.( * 은 공백을 의미합니다.)

1 2 3

4 5 6

8 7 *

여기서 앞의 숫자가 뒤의 숫자보다 큰 경우를 inversion 이라고 합니다.

=> ex : (1, 2) 의 경우 inversion이 아닙니다. 하지만 (8, 7) 의 경우 inversion이 맞습니다.

이런 식으로 해당 퍼즐에서 inversion의 개수가 몇 개인지 먼저 체크합니다.

 

다음으로 N x N 퍼즐일 때, N이 홀수인지 짝수인지에 따라 규칙이 달라집니다.

1. N이 홀수라면, 전체 inversion의 수가 짝수가 나올 때 그 퍼즐은 해결이 가능합니다.(즉, 홀수라면 퍼즐 해결이 불가합니다)

2. N이 짝수라면, 퍼즐 공백의 위치가 짝수 행(맨 아래에서 위로 세야 합니다.) 일 때 전체 inversion의 수가 홀수라면 그 퍼즐은 해결이 가능합니다.

3. N이 짝수라면, 퍼즐 공백의 위치가 홀수 행(맨 아래에서 위로 세야 합니다.) 일 때 전체 inversion의 수가 짝수라면 그 퍼즐은 해결이 가능합니다.

 

N이 홀수라면 전체 inversion이 짝수인지만 확인하면 끝입니다. N이 짝수라면 공백의 위치를 확인해야 하는데 저희는 공백이 항상 맨 마지막에 있게 된다는 것을 유의합시다. 또한 N이 짝수이면 N x N 의 맨 마지막 행은 무조건 짝수입니다.

즉, 저희는 1번, 2번 규칙만 유의하여 코드를 작성하면 됩니다.

 

36 ~ 40 번째 라인에서 총 inversion의 수를 구합니다.

42 번째 라인은 N이 짝수인지 홀수인지를 구하는 코드입니다.

43 번째 라인은 규칙 3을 적용하는 코드입니다.

47 번째 라인은 규칙 1을 적용하는 코드입니다.

 

가급적 확장이 용이하게 만들기 위해 노력했지만 미흡한 상태입니다. 개선 사항이 있으면 언제든 알려주세요.

 

 

system("cls") 함수를 이용해 콘솔 창을 모두 정리한 후 다시 출력합니다.

66 ~ 77 번째 라인에서 게임 클리어 유무를 확인합니다. 모든 수가 순서대로 정렬된다면 게임 클리어입니다.

 

 

아래 코드는 플레이어로부터 w, a, s, d, q 를 입력받는 부분입니다.

자세한 설명은 모두 주석으로 처리되어 있으므로 주석을 참고하여 주세요.

 

이후의 코드는 간단한 switch문으로 작성해서 별다른 분석할 내용은 없습니다.

사용자의 Capslock 버튼이 눌러있을 경우를 대비해 대소문자를 구분하지 않고 모두 받는다는 것만 유의해주세요.

 

 

잘못된 부분이나 개선 사항은 언제나 편하게 댓글로 지적해주세요.

감사합니다.

 

출처

(7) C언어/C++강의 15화 숫자퍼즐게임 [어소트락 게임아카데미] - YouTube